Memesan catatan secara acak dalam sebuah tabel

Kebutuhan umum saat menggunakan database adalah mengakses catatan secara berurutan. Misalnya, jika saya memiliki blog, saya ingin dapat memesan ulang posting blog saya dalam urutan acak. Entri-entri ini sering memiliki banyak hubungan, jadi database relasional sepertinya masuk akal.

Solusi umum yang saya lihat adalah menambahkan kolom integer order:

CREATE TABLE AS your_table (id, title, sort_order)
AS VALUES
  (0, 'Lorem ipsum',   3),
  (1, 'Dolor sit',     2),
  (2, 'Amet, consect', 0),
  (3, 'Elit fusce',    1);

Kemudian, kita bisa mengurutkan baris dengan ordermengatur urutannya.

Namun, ini tampak canggung:

• Jika saya ingin memindahkan record 0 ke awal, saya harus menyusun ulang setiap record
• Jika saya ingin menyisipkan catatan baru di tengah, saya harus menyusun ulang setiap catatan setelahnya
• Jika saya ingin menghapus catatan, saya harus menyusun ulang setiap catatan setelahnya

Sangat mudah untuk membayangkan situasi seperti:

• Dua catatan memiliki hal yang sama order
• Ada celah di orderantara catatan

Ini bisa terjadi dengan cukup mudah karena sejumlah alasan.

Ini adalah pendekatan yang diambil oleh aplikasi seperti Joomla:

Anda bisa berpendapat bahwa antarmuka di sini buruk, dan bahwa alih-alih manusia secara langsung mengedit angka, mereka harus menggunakan panah atau seret-dan-jatuhkan — dan Anda mungkin benar. Namun di balik layar, hal yang sama terjadi.

Beberapa orang telah mengusulkan menggunakan desimal untuk menyimpan pesanan, sehingga Anda dapat menggunakan "2.5" untuk menyisipkan catatan di antara catatan di urutan 2 dan 3. Dan sementara itu sedikit membantu, itu bisa dibilang lebih berantakan karena Anda bisa berakhir dengan desimal aneh (di mana Anda berhenti? 2,75? 2,875? 2,8125?)

Apakah ada cara yang lebih baik untuk menyimpan pesanan di meja?

Jika saya ingin memindahkan record 0 ke awal, saya harus menyusun ulang setiap record

Tidak, ada cara yang lebih sederhana.

update your_table
set order = -1 
where id = 0;

Jika saya ingin menyisipkan catatan baru di tengah, saya harus menyusun ulang setiap catatan setelahnya

Itu benar, kecuali jika Anda menggunakan tipe data yang mendukung nilai "antara". Jenis float dan numerik memungkinkan Anda memperbarui nilai menjadi, katakanlah, 2.5. Tetapi varchar (n) juga berfungsi. (Pikirkan 'a', 'b', 'c'; lalu pikirkan 'ba', 'bb', 'bc'.)

Jika saya ingin menghapus catatan, saya harus menyusun ulang setiap catatan setelahnya

Tidak, ada cara yang lebih sederhana. Hapus saja barisnya. Baris yang tersisa masih akan mengurutkan dengan benar.

Sangat mudah untuk membayangkan situasi seperti:

Dua catatan memiliki urutan yang sama

Kendala yang unik dapat mencegah hal itu.

Ada celah dalam urutan antara catatan

Kesenjangan tidak berpengaruh pada bagaimana dbms mengurutkan nilai dalam kolom.

Beberapa orang telah mengusulkan menggunakan desimal untuk menyimpan pesanan, sehingga Anda dapat menggunakan "2.5" untuk menyisipkan catatan di antara catatan di urutan 2 dan 3. Dan sementara itu sedikit membantu, itu bisa dibilang lebih berantakan karena Anda bisa berakhir dengan desimal aneh (di mana Anda berhenti? 2,75? 2,875? 2,8125?)

Anda tidak berhenti sampai Anda harus melakukannya. Dbms tidak memiliki masalah mengurutkan nilai yang memiliki 2, 7, atau 15 tempat setelah titik desimal.

Saya pikir masalah Anda yang sebenarnya adalah Anda ingin melihat nilai dalam urutan yang diurutkan sebagai bilangan bulat. Kamu bisa melakukannya.

create table your_table (
  id int primary key, 
  title varchar(13), 
  sort_order float
);

insert into your_table values
(0, 'Lorem ipsum', 2.0),
(1, 'Dolor sit', 1.5),
(2, 'Amet, consect', 0.0),
(3, 'Elit fusce', 1.0);

-- This windowing function will "transform" the floats into sorted integers.
select id, title,
       row_number() over (order by sort_order)
from your_table

Ini sangat sederhana. Anda perlu memiliki struktur "lubang kardinalitas":

Anda harus memiliki 2 kolom:

1. pk = 32bit integer
2. order = 64bit bigint( tidak double )

Sisipkan / perbarui

1. Saat memasukkan catatan baru pertama, atur order = round(max_bigint / 2).
2. Saat memasukkan di awal tabel, atur order = round("order of first record" / 2)
3. Saat memasukkan di akhir tabel, atur order = round("max_bigint - order of last record" / 2) 4) Saat memasukkan di tengah, aturorder = round("order of record before - order of record after" / 2)

Metode ini memiliki kardinalitas yang sangat besar. Jika Anda memiliki kendala kendala atau jika Anda berpikir apa yang Anda miliki dengan kardinalitas kecil, Anda dapat membangun kembali kolom pesanan (normalisasi).

Dalam situasi maksimal dengan normalisasi (dengan struktur ini) Anda dapat memiliki "lubang kardinalitas" dalam 32 bit.

Ingatlah untuk tidak menggunakan tipe floating point - pesanan harus bernilai tepat!

Secara umum, pemesanan dilakukan sesuai dengan beberapa informasi dalam catatan, judul, ID, atau apa pun yang sesuai untuk situasi tertentu.

Jika Anda membutuhkan pemesanan khusus, menggunakan kolom bilangan bulat tidak seburuk kelihatannya. Misalnya, untuk memberi ruang bagi catatan untuk masuk ke tempat ke-5, Anda dapat melakukan sesuatu seperti:

update table_1 set place = place + 1 where place > 5.

Semoga Anda dapat mendeklarasikan kolom menjadi uniquedan mungkin memiliki prosedur untuk membuat pengaturan ulang "atom". Rinciannya tergantung pada sistem tetapi itu adalah ide umum.

... bisa dibilang lebih berantakan karena Anda bisa berakhir dengan desimal aneh (di mana Anda berhenti? 2,75? 2,875? 2,8125?)

Siapa peduli? Angka-angka ini hanya ada untuk ditangani oleh komputer, jadi tidak masalah berapa banyak digit fraksional yang mereka miliki atau seberapa jeleknya mereka bagi kita.

Menggunakan nilai desimal berarti bahwa untuk memindahkan item F antara item J dan K yang perlu Anda lakukan adalah memilih nilai pesanan untuk J dan K kemudian rata-rata mereka kemudian memperbarui F. Dua pernyataan SELECT dan satu pernyataan UPDATE (mungkin dilakukan menggunakan isolasi serializable untuk menghindari kebuntuan).

Jika Anda ingin melihat bilangan bulat daripada fraksi dalam output maka hitung bilangan bulat di aplikasi klien atau gunakan fungsi ROW_NUMBER () atau RANK () (jika RDBMS Anda memasukkannya).

Dalam proyek saya sendiri, saya berencana untuk mencoba solusi yang mirip dengan solusi angka desimal, tetapi menggunakan byte-array sebagai gantinya:

def pad(x, x_len, length):
    if x_len >= length:
        return x
    else:
        for _ in range(length - x_len):
            x += b"\x00"
        return x

def order_index(_from, _to, count, length=None):
    assert _from != _to
    assert _from < _to

    if not length:
        from_len = len(_from)
        to_len = len(_to)
        length = max(from_len, to_len)

        _from = pad(_from, from_len, length)
        _to = pad(_to, to_len, length)

    from_int = int.from_bytes(_from, "big")
    to_int = int.from_bytes(_to, "big")
    inc = (to_int - from_int)//(count + 1)
    if not inc:
        length += 1
        _from += b"\x00"
        _to += b"\x00"
        return order_index(_from, _to, count, length)

    return (int.to_bytes(from_int + ((x+1)*inc), length, "big") for x in range(count))

>>> index = order_index(b"A", b"Z", 24)
>>> [x for x in index]
[b'B', b'C', b'D', b'E', b'F', b'G', b'H', b'I', b'J', b'K', b'L', b'M', b'N', b'O', b'P', b'Q', b'R', b'S', b'T', b'U', b'V', b'W', b'X', b'Y']
>>> 
>>> index = order_index(b"A", b"Z", 25)
>>> [x for x in index]
[b'A\xf6', b'B\xec', b'C\xe2', b'D\xd8', b'E\xce', b'F\xc4', b'G\xba', b'H\xb0', b'I\xa6', b'J\x9c', b'K\x92', b'L\x88', b'M~', b'Nt', b'Oj', b'P`', b'QV', b'RL', b'SB', b'T8', b'U.', b'V$', b'W\x1a', b'X\x10', b'Y\x06']

Idenya adalah bahwa Anda tidak akan pernah kehabisan nilai di antara yang mungkin karena dan Anda hanya menambahkan b"\x00"ke catatan yang terlibat jika Anda membutuhkan lebih banyak nilai. ( inttidak terikat dalam Python 3, jika tidak Anda harus memilih sepotong byte pada akhir untuk membandingkan, dengan asumsi bahwa, antara dua nilai yang berdekatan, perbedaan akan dikemas menjelang akhir.)

Misalnya, Anda memiliki dua catatan, b"\x00"dan b"\x01", dan Anda ingin catatan untuk pergi di antara mereka. Tidak ada nilai yang tersedia di antara 0x00dan 0x01, jadi Anda menambahkan b"\x00"keduanya, dan sekarang Anda memiliki banyak nilai yang dapat Anda gunakan untuk menyisipkan nilai-nilai baru.

>>> records = [b"\x00", b"\x01", b"\x02"]
>>> values = [x for x in order_index(records[0], records[1], 3)]
>>> records = records + values
>>> records.sort()
>>> records
[b'\x00', b'\x00@', b'\x00\x80', b'\x00\xc0', b'\x01', b'\x02']

Basis data dapat dengan mudah mengurutkannya karena semuanya berakhir dengan urutan leksikografis. Jika Anda menghapus catatan, itu masih dalam urutan. Dalam proyek saya, saya telah membuat b"\x00"dan b"\xff"sebagai FIRSTdan LASTmencatat, untuk menggunakannya sebagai nilai virtual "dari" dan "ke" untuk menambahkan / menambahkan catatan baru:

>>> records = []
>>> value = next(order_index(FIRST, LAST, 1))
>>> value
b'\x7f'
>>> records.append(value)
>>> value = next(order_index(records[0], LAST, 1))
>>> value
b'\xbf'
>>> records.append(value)
>>> records.sort()
>>> records
[b'\x7f', b'\xbf']
>>> value = next(order_index(FIRST, records[0], 1))
>>> value
b'?'
>>> records.append(value)
>>> records.sort()
>>> records
[b'?', b'\x7f', b'\xbf']

Saya menemukan jawaban ini jauh lebih baik. Mengutip sepenuhnya:

Database dioptimalkan untuk hal-hal tertentu. Memperbarui banyak baris dengan cepat adalah salah satunya. Ini menjadi benar terutama ketika Anda membiarkan database melakukan tugasnya.

Mempertimbangkan:

order song
1     Happy Birthday
2     Beat It
3     Never Gonna Give You Up
4     Safety Dance
5     Imperial March

Dan Anda ingin pindah Beat Itke akhir, Anda akan memiliki dua pertanyaan:

update table 
  set order = order - 1
  where order >= 2 and order <= 5;

update table
  set order = 5
  where song = 'Beat It'

Dan itu saja. Ini berskala sangat baik dengan jumlah yang sangat besar. Coba letakkan beberapa ribu lagu dalam daftar putar hipotetis di database Anda dan lihat berapa lama waktu yang dibutuhkan untuk memindahkan lagu dari satu lokasi ke lokasi lain. Karena ini memiliki bentuk yang sangat standar:

update table 
  set order = order - 1
  where order >= ? and order <= ?;

update table
  set order = ?
  where song = ?

Anda memiliki dua pernyataan siap yang dapat Anda gunakan kembali dengan sangat efisien.

Ini memberikan beberapa keuntungan signifikan - urutan tabel adalah sesuatu yang dapat Anda alasankan. Lagu ketiga memiliki order3, selalu. Satu-satunya cara untuk menjamin ini adalah dengan menggunakan bilangan bulat berturut-turut sebagai pesanan. Menggunakan daftar yang ditautkan pseudo atau angka desimal atau bilangan bulat dengan celah tidak akan membuat Anda menjamin properti ini; dalam kasus ini satu-satunya cara untuk mendapatkan lagu ke-n adalah menyortir seluruh tabel dan mendapatkan catatan ke-n.

Dan sungguh, ini jauh lebih mudah daripada yang Anda pikirkan. Sangat mudah untuk mengetahui apa yang ingin Anda lakukan, untuk menghasilkan dua pernyataan pembaruan dan bagi orang lain untuk melihat dua pernyataan pembaruan tersebut dan menyadari apa yang sedang dilakukan.