Menyimpan daftar yang dapat dipesan kembali dalam database

Saya sedang mengerjakan sistem daftar harapan, di mana pengguna dapat menambahkan item ke berbagai daftar keinginan mereka, dan saya berencana untuk mengizinkan pengguna memesan kembali item-item tersebut di kemudian hari. Saya tidak benar-benar yakin tentang cara terbaik untuk menyimpan tentang ini dalam database sementara tetap cepat dan tidak berubah menjadi berantakan (aplikasi ini akan digunakan oleh basis pengguna yang cukup besar, jadi saya tidak ingin itu turun untuk membersihkan barang).

Saya awalnya mencoba positionkolom, tetapi sepertinya itu akan sangat tidak efisien karena harus mengubah nilai posisi setiap item lain ketika Anda memindahkannya.

Saya telah melihat orang-orang menggunakan referensi-diri untuk merujuk pada nilai sebelumnya (atau selanjutnya), tetapi sekali lagi, sepertinya Anda harus memperbarui banyak item lain dalam daftar.

Solusi lain yang saya lihat adalah menggunakan angka desimal dan hanya menempelkan item di celah di antara mereka, yang tampaknya merupakan solusi terbaik sejauh ini, tapi saya yakin harus ada cara yang lebih baik.

Saya akan mengatakan daftar tipikal akan berisi hingga sekitar 20 atau lebih item, dan saya mungkin akan membatasi hingga 50. Pemesanan ulang akan menggunakan drag dan drop dan mungkin akan dilakukan dalam batch untuk mencegah kondisi balapan dan semacamnya dari permintaan ajax. Saya menggunakan postgres (di heroku) jika itu penting.

Adakah yang punya ide?

Sorakan untuk bantuan!

Pertama, jangan mencoba melakukan sesuatu yang pintar dengan angka desimal, karena mereka akan membuat Anda marah. REALdan DOUBLE PRECISIONtidak tepat dan mungkin tidak mewakili dengan tepat apa yang Anda masukkan ke dalamnya. NUMERICtepat, tetapi urutan gerakan yang tepat akan membuat Anda kehabisan presisi dan implementasi Anda akan rusak parah.

Membatasi gerakan ke atas dan ke bawah membuat seluruh operasi sangat mudah. Untuk daftar item yang diberi nomor urut, Anda dapat memindahkan item ke atas dengan mengurangi posisinya dan menambah jumlah posisi dari apa pun yang muncul dari penurunan sebelumnya. (Dengan kata lain, barang 5akan menjadi 4dan apa yang item yang 4menjadi 5, efektif swap sebagai Morons dijelaskan dalam jawabannya.) Pindah ke bawah akan menjadi sebaliknya. Buat indeks tabel Anda dengan apa pun yang secara unik mengidentifikasi daftar dan posisi dan Anda dapat melakukannya dengan dua UPDATEdi dalam transaksi yang akan berjalan sangat cepat. Kecuali jika pengguna Anda mengatur ulang daftar mereka dengan kecepatan manusia super, ini tidak akan menyebabkan banyak beban.

Gerakan seret-dan-jatuhkan (mis., Memindahkan item 6untuk duduk di antara item 9dan 10) agak rumit dan harus dilakukan secara berbeda tergantung pada apakah posisi baru di atas atau di bawah yang lama. Dalam contoh di atas, Anda harus membuka lubang dengan menambah semua posisi lebih besar dari 9, memperbarui 6posisi item menjadi yang baru 10dan kemudian mengurangi posisi segala sesuatu yang lebih besar daripada 6mengisi tempat yang kosong. Dengan pengindeksan yang sama yang saya jelaskan sebelumnya, ini akan cepat. Anda benar-benar dapat membuat ini berjalan sedikit lebih cepat daripada yang saya jelaskan dengan meminimalkan jumlah baris yang disentuh transaksi, tetapi itu adalah optimasi mikro yang tidak Anda butuhkan sampai Anda dapat membuktikan ada hambatan.

Either way, mencoba mengungguli database dengan solusi buatan rumah, terlalu pintar untuk setengah biasanya tidak mengarah pada kesuksesan. Database bernilai garam mereka telah ditulis dengan cermat untuk melakukan operasi ini dengan sangat, sangat cepat oleh orang-orang yang sangat, sangat pandai dalam hal ini.

Jawaban yang sama dari sini https://stackoverflow.com/a/49956113/10608

Solusi: buat indexstring (karena string, pada dasarnya, memiliki "presisi arbitrer" yang tak terbatas). Atau jika Anda menggunakan int, kenaikan index100 bukannya 1.

Masalah kinerja adalah ini: tidak ada nilai "di antara" antara dua item yang diurutkan.

item      index
-----------------
gizmo     1
              <<------ Oh no! no room between 1 and 2.
                       This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

Sebaliknya, lakukan seperti ini (solusi yang lebih baik di bawah):

item      index
-----------------
gizmo     100
              <<------ Sweet :). I can re-order 99 (!) items here
                       without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

Bahkan lebih baik: inilah cara Jira memecahkan masalah ini. "Peringkat" mereka (apa yang Anda sebut indeks) adalah nilai string yang memungkinkan satu ton ruang bernapas di antara item-item yang diberi peringkat.

Berikut ini adalah contoh nyata dari database jira tempat saya bekerja

   id    | jira_rank
---------+------------
 AP-2405 | 0|hzztxk:
 ES-213  | 0|hzztxs:
 AP-2660 | 0|hzztzc:
 AP-2688 | 0|hzztzk:
 AP-2643 | 0|hzztzs:
 AP-2208 | 0|hzztzw:
 AP-2700 | 0|hzztzy:
 AP-2702 | 0|hzztzz:
 AP-2411 | 0|hzztzz:i
 AP-2440 | 0|hzztzz:r

Perhatikan contoh ini hzztzz:i. Keuntungan dari peringkat string adalah Anda kehabisan ruang di antara dua item, Anda masih tidak perlu peringkat ulang hal lain. Anda baru saja mulai menambahkan lebih banyak karakter ke string untuk mempersempit fokus.

Saya telah melihat orang-orang menggunakan referensi-diri untuk merujuk pada nilai sebelumnya (atau selanjutnya), tetapi sekali lagi, sepertinya Anda harus memperbarui banyak item lain dalam daftar.

Mengapa? Katakanlah Anda mengambil pendekatan tabel linked-list dengan kolom (listID, itemID, nextItemID).

Memasukkan item baru ke dalam daftar membutuhkan biaya satu kali insert, dan satu baris yang dimodifikasi.

Memposisikan ulang item membutuhkan tiga modifikasi baris (item dipindahkan, item sebelum itu, dan item sebelum lokasi baru).

Menghapus satu item berharga satu penghapusan dan satu baris dimodifikasi.

Biaya-biaya ini tetap sama terlepas dari apakah daftar itu memiliki 10 item atau 10.000 item. Dalam ketiga kasus ada satu modifikasi kurang jika baris target adalah item daftar pertama. Jika Anda lebih sering beroperasi pada item daftar terakhir , mungkin bermanfaat untuk menyimpan previtemID daripada berikutnya.

"Tapi sepertinya itu akan sangat tidak efisien"

Apakah Anda mengukurnya ? Atau itu hanya dugaan? Jangan membuat asumsi seperti itu tanpa bukti.

"20 hingga 50 item per daftar"

Jujur, itu bukan "banyak item", bagi saya itu terdengar sangat sedikit.

Saya sarankan Anda tetap menggunakan pendekatan "kolom posisi" (jika itu implementasi paling sederhana untuk Anda). Untuk ukuran daftar sekecil itu, jangan mulai mengoptimalkan yang tidak perlu sebelum Anda mengalami masalah kinerja nyata

Ini benar-benar masalah skala, dan kasus penggunaan ..

Berapa banyak item yang Anda harapkan dalam daftar? Jika jutaan, saya pikir gong rute desimal adalah yang jelas.

Jika 6 maka bilangan ulang bilangan bulat adalah pilihan yang jelas. s Juga pertanyaannya adalah bagaimana daftar atau disusun ulang. Jika Anda menggunakan panah atas dan bawah (bergerak naik atau turun satu slot pada suatu waktu), saya akan menggunakan bilangan bulat lalu bertukar dengan prev (atau berikutnya) saat bergerak.

Juga seberapa sering Anda melakukan, jika pengguna dapat membuat 250 perubahan kemudian melakukan sekaligus, daripada yang saya katakan bilangan bulat dengan penomoran ulang lagi ...

tl; dr: Perlu info lebih lanjut.

Sunting: "Daftar keinginan" terdengar seperti banyak daftar kecil (anggapan, ini mungkin salah) .. Jadi saya katakan Integer dengan penomoran ulang. (Setiap daftar berisi Posisi sendiri)

Jika tujuannya adalah untuk meminimalkan jumlah operasi basis data per operasi pemesanan ulang:

Berasumsi bahwa

• Semua item belanja dapat disebutkan dengan integer 32-bit.
• Ada batas ukuran maksimum untuk daftar keinginan pengguna. (Saya melihat beberapa situs web populer menggunakan 20 - 40 item sebagai batasan)

Simpan daftar keinginan yang diurutkan pengguna sebagai urutan bilangan bulat (array bilangan bulat) dalam satu kolom. Setiap kali daftar keinginan disusun ulang, seluruh array (baris tunggal; kolom tunggal) diperbarui - yang harus dilakukan dengan pembaruan SQL tunggal.

https://www.postgresql.org/docs/current/static/arrays.html

Jika tujuannya berbeda, tetap dengan pendekatan "kolom posisi".

Mengenai "kecepatan", pastikan untuk melakukan tolok ukur pendekatan prosedur tersimpan. Meskipun mengeluarkan 20+ pembaruan terpisah untuk satu pengacakan daftar keinginan mungkin lambat, mungkin ada cara cepat menggunakan prosedur tersimpan.

Oke, saya menghadapi masalah rumit ini baru-baru ini, dan semua jawaban dalam posting tanya jawab ini memberi banyak inspirasi. Cara saya melihatnya, setiap solusi memiliki pro dan kontra.

• Jika positionbidang harus berurutan tanpa celah, maka pada dasarnya Anda perlu memesan ulang seluruh daftar. Ini adalah operasi O (N). Keuntungannya adalah pihak klien tidak perlu logika khusus untuk mendapatkan pesanan.

• Jika kita ingin menghindari operasi O (N) TETAPI tetap mempertahankan urutan yang tepat, salah satu pendekatannya adalah menggunakan "referensi-diri untuk merujuk pada nilai sebelumnya (atau selanjutnya)". Ini adalah skenario daftar tertaut buku teks. Secara desain, itu TIDAK akan menimbulkan "banyak item lain dalam daftar". Namun, ini membutuhkan sisi klien (layanan web atau mungkin aplikasi seluler) untuk menerapkan logika lintasan daftar-tertaut untuk mendapatkan pesanan.

• Beberapa variasi tidak menggunakan referensi yaitu daftar tertaut. Mereka memilih untuk mewakili seluruh pesanan sebagai gumpalan mandiri, seperti JSON-array-in-a-string [5,2,1,3,...]; pesanan tersebut kemudian akan disimpan di tempat yang terpisah. Pendekatan ini juga memiliki efek samping yang memerlukan kode sisi klien untuk mempertahankan gumpalan pesanan yang terpisah.

• Dalam banyak kasus, kita tidak benar-benar perlu menyimpan urutan yang tepat, kita hanya perlu mempertahankan peringkat relatif di antara setiap catatan. Oleh karena itu kami dapat memungkinkan kesenjangan antara rekaman berurutan. Variasi meliputi: (1) menggunakan integer dengan celah seperti 100, 200, 300 ... tetapi Anda akan dengan cepat kehabisan celah dan kemudian perlu proses pemulihan; (2) menggunakan desimal yang dilengkapi dengan celah alami, tetapi Anda harus memutuskan apakah Anda dapat hidup dengan batasan presisi yang akhirnya; (3) menggunakan peringkat berbasis string seperti yang dijelaskan dalam jawaban ini tetapi hati-hati dengan perangkap implementasi yang rumit .

• Jawaban sebenarnya bisa "tergantung". Tinjau kembali kebutuhan bisnis Anda. Misalnya, jika ini adalah sistem daftar keinginan, secara pribadi saya akan dengan senang hati menggunakan sistem yang dikelola oleh hanya beberapa peringkat sebagai "must-have", "good-to-have", "mungkin-nanti", dan kemudian menyajikan barang-barang tanpa khususnya memesan di dalam setiap peringkat. Jika ini adalah sistem pengiriman, Anda dapat menggunakan waktu pengiriman dengan sangat baik sebagai peringkat kasar yang datang dengan kesenjangan alami (dan pencegahan konflik alam karena tidak ada pengiriman yang akan terjadi pada saat yang sama). Jarak tempuh Anda mungkin beragam.

Gunakan nomor titik apung untuk kolom posisi.

Anda kemudian dapat menyusun ulang daftar yang hanya mengubah kolom posisi di baris "pindah".

Pada dasarnya jika pengguna Anda ingin memposisikan "merah" setelah "biru" tetapi sebelum "kuning"

Maka Anda hanya perlu menghitung

red.position = ((yellow.position - blue.position) / 2) + blue.position

Setelah beberapa juta posisi ulang, Anda mungkin mendapatkan angka floating point yang sangat kecil sehingga tidak ada "antara" - tetapi ini hampir sama dengan melihat unicorn.

Anda bisa mengimplementasikan ini menggunakan bidang integer dengan celah awal katakanlah 1000. Jadi oredring awal Anda akan menjadi 1000-> biru, 2000-> Kuning, 3000-> Merah. Setelah "bergerak" Merah demi biru Anda akan memiliki 1000-> biru, 1500-> Merah, 2000-> Kuning.

Masalahnya adalah bahwa dengan kesenjangan awal yang tampaknya besar 1000 sesedikit 10 gerakan akan membawa Anda ke situasi seperti 1000-> biru, 1001-puce, 1004-> biege ...... di mana Anda tidak akan lagi dapat untuk memasukkan apa pun setelah "biru" tanpa memberi nomor ulang seluruh daftar. Menggunakan angka floating point akan selalu ada titik "setengah" antara dua posisi.

Sementara OP secara singkat menyentuh gagasan menggunakan Linked-List untuk menyimpan sort-order, ia memiliki banyak keuntungan untuk kasus-kasus di mana item akan sering dipesan ulang.

Saya telah melihat orang-orang menggunakan referensi-diri untuk merujuk pada nilai sebelumnya (atau selanjutnya), tetapi sekali lagi, sepertinya Anda harus memperbarui banyak item lain dalam daftar.

Masalahnya adalah - Anda tidak ! Saat menggunakan daftar-tertaut, penyisipan, penghapusan, dan pemesanan ulang adalah O(1)operasi, dan integritas referensial yang dipasok oleh basis data memastikan tidak ada referensi yang rusak, catatan yatim, atau loop.

Ini sebuah contoh:

CREATE TABLE Wishlists (
  WishlistId int           NOT NULL IDENTITY(1,1) PRIMARY KEY,
  [Name]     nvarchar(200) NOT NULL
);

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId );

 -----

SET IDENTITY_INSERT Wishlists ON;

INSERT INTO Wishlists ( WishlistId, [Name] ) VALUES
  ( 1, 'Wishlist 1' ),
  ( 2, 'Wishlist 2' );

SET IDENTITY_INSERT Wishlists OFF;

SET IDENTITY_INSERT WishlistItems ON;

INSERT INTO WishlistItems ( ItemId, WishlistId, [Text], SortAfter ) VALUES
( 1, 1, 'One', NULL ),
( 2, 1, 'Two', 1 ),
( 3, 1, 'Three', 2 ),
( 4, 1, 'Four', 3 ),
( 5, 1, 'Five', 4 ),
( 6, 1, 'Six', 5 ),
( 7, 1, 'Seven', 6 ),
( 8, 1, 'Eight', 7 );

SET IDENTITY_INSERT WishlistItems OFF;

Perhatikan yang berikut ini:

• Menggunakan kunci primer gabungan dan kunci asing di FK_Sortinguntuk mencegah item agar tidak sengaja merujuk ke item induk yang salah.
• The UNIQUE INDEX UX_Sortingmelakukan dua peran:
  • Karena memungkinkan NULLnilai tunggal, setiap daftar hanya dapat memiliki 1 item "head".
  • Ini mencegah dua atau lebih item dari mengklaim berada di tempat penyortiran yang sama (dengan mencegah SortAfternilai duplikat ).

Keuntungan utama dari pendekatan ini:

• Tidak pernah membutuhkan penyeimbangan kembali atau pemeliharaan - seperti dengan intatau real-sortir pesanan yang akhirnya kehabisan ruang antara item setelah pemesanan ulang sering.
• Hanya barang yang dipesan ulang (dan saudara mereka) yang perlu diperbarui.

Pendekatan ini memang memiliki kelemahan, namun:

• Anda hanya dapat mengurutkan daftar ini dalam SQL menggunakan CTE Rekursif karena Anda tidak dapat melakukan secara langsung ORDER BY.
  • Sebagai solusinya, Anda bisa membuat pembungkus VIEWatau TVF yang menggunakan CTE untuk menambahkan turunan yang mengandung urutan tambahan - tetapi ini akan mahal untuk digunakan dalam operasi besar.
• Anda harus memuat seluruh daftar ke dalam program Anda untuk menampilkannya - Anda tidak dapat beroperasi pada bagian dari baris karena dengan demikian SortAfterkolom akan merujuk ke item yang tidak dimuat ke dalam program Anda.
  • Namun memuat semua item untuk daftar mudah karena kunci primer komposit (yaitu lakukan saja SELECT * FROM WishlistItems WHERE WishlistId = @wishlistToLoad).
• Melakukan operasi apa pun saat UX_Sortingdiaktifkan memerlukan dukungan DBMS untuk Kendala yang Ditangguhkan.
  • yaitu implementasi ideal dari pendekatan ini tidak akan bekerja di SQL Server sampai mereka menambahkan kembali dukungan untuk Deferrable Constraints dan indeks.
  • Solusinya adalah membuat Indeks Unik sebagai Indeks yang Difilter yang memungkinkan beberapa NULLnilai di kolom - yang sayangnya berarti bahwa Daftar dapat memiliki beberapa item KEPALA.
    • Solusi untuk solusi ini adalah menambahkan kolom ketiga Stateyang merupakan flag sederhana untuk menyatakan jika item daftar "aktif" atau tidak - dan indeks unik mengabaikan item yang tidak aktif.
  • Ini adalah sesuatu yang digunakan SQL Server untuk mendukung kembali pada 1990-an dan kemudian mereka secara tidak sengaja menghapus dukungan untuk itu.

Solusi 1: Butuh kemampuan untuk melakukan hal-hal sepele ORDER BY.

Berikut ini VIEW menggunakan CTE rekursif yang menambahkan SortOrderkolom:

CREATE VIEW OrderableWishlistItems AS 

    WITH c ( ItemId, WishlistId, [Text], SortAfter, SortOrder )
    AS
    (
        SELECT
              ItemId, WishlistId, [Text], SortAfter, 1 AS SortOrder
        FROM
              WishlistItems
        WHERE
              SortAfter IS NULL

        UNION ALL

        SELECT
              i.ItemId, i.WishlistId, i.[Text], i.SortAfter, c.SortOrder + 1
        FROM
              WishlistItems AS i
              INNER JOIN c ON
                  i.WishlistId = c.WishlistId
                  AND
                  i.SortAfter = c.ItemId
    )
    SELECT
        ItemId, WishlistId, [Text], SortAfter, SortOrder
    FROM
        c;

Anda bisa menggunakan LIHAT ini di kueri lain di mana Anda perlu mengurutkan nilai menggunakan ORDER BY:

Query:

    SELECT * FROM OrderableWishlistItems

Results:

    ItemId  WishlistId  Text        SortAfter   SortOrder
    1       1           One         (null)      1
    2       1           Two             1       2
    3       1           Three           2       3
    4       1           Four            3       4
    5       1           Five            4       5
    6       1           Six             5       6
    7       1           Seven           6       7
    8       1           Eight           7       8

Solusi 2: Mencegah UNIQUE INDEXkendala pelanggaran saat melakukan operasi:

Tambahkan Statekolom ke WishlistItemstabel. Kolom ditandai sebagai HIDDENsebagian besar alat ORM (seperti Entity Framework) tidak akan memasukkannya saat membuat model, misalnya.

CREATE TABLE WishlistItems (
  ItemId     int           NOT NULL IDENTITY(1,1),
  WishlistId int           NOT NULL,
  Text       nvarchar(200) NOT NULL,
  SortAfter  int               NULL,
  [State]    bit           NOT NULL HIDDEN,

  CONSTRAINT PK_WishlistItem PRIMARY KEY ( ItemId, WishlistId ),
  CONSTRAINT FK_Wishlist_WishlistItem FOREIGN KEY ( WishlistId ) REFERENCES Wishlists ( WishlistId ),
  CONSTRAINT FK_Sorting FOREIGN KEY ( SortAfter, WishlistId ) REFERENCES WishlistItems ( ItemId, WishlistId )
);

CREATE UNIQUE INDEX UX_Sorting ON WishlistItems ( SortAfter, WishlistId ) WHERE [State] = 1;

Operasi:

Menambahkan item baru ke ujung daftar:

1. Muat daftar terlebih dahulu untuk menentukan ItemIditem terakhir saat ini dalam daftar dan simpan @tailItemId- atau gunakan SELECT MAX( SortOrder ) FROM OrderableWishlistItems WHERE WishlistId = @listId.
2. INSERT INTO WishlistItems ( WishlistId, [Text], SortAfter ) VALUES ( @listId, @text, @tailItemId ).

Menyusun ulang item 4 menjadi di bawah item 7

BEGIN TRANSACTION

    DECLARE @itemIdToMove int = 4
    DECLARE @itemIdToMoveAfter int = 7

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToMove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId IN ( @itemIdToMove , @itemIdToMoveAfter )

    UPDATE WishlistItems SET [SortAfter] = @itemIdToMove WHERE ItemId = @itemIdToMoveAfter 

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToMove 

    UPDATE WishlistItems SET [State] = 1 WHERE ItemId IN ( @itemIdToMove, @itemIdToMoveAfter )

COMMIT;

Menghapus item 4 dari tengah daftar:

Jika suatu item ada di ujung ekor daftar (yaitu di mana NOT EXISTS ( SELECT 1 FROM WishlistItems WHERE SortAfter = @itemId )) maka Anda dapat melakukan satu DELETE.

Jika suatu item memiliki item yang diurutkan setelahnya, Anda melakukan langkah yang sama seperti menata ulang item, kecuali Anda DELETEsetelah itu alih-alih pengaturan State = 1;.

BEGIN TRANSACTION

    DECLARE @itemIdToRemove int = 4

    DECLARE @prev int = ( SELECT SortAfter FROM WishlistItems WHERE ItemId = @itemIdToRemove )

    UPDATE WishlistItems SET [State] = 0 WHERE ItemId = @itemIdToRemove

    UPDATE WishlistItems SET [SortAfter] = @prev WHERE SortAfter = @itemIdToRemove

    DELETE FROM WishlistItems WHERE ItemId = @itemIdToRemove

COMMIT;