it-swarm-eu.dev

Jak navrhnout databázi pro uložení tříděného seznamu?

Hledám uložení tříděného seznamu do databáze. Chci provádět následující operace efektivně.

  1. Vložit (x) - Vloží záznam x do tabulky
  2. Smazat (x) - Smazat záznam x z tabulky
  3. Before (x, n) - Vraťte záznamy „n“ před záznamem x v seřazeném seznamu.
  4. After (x, n) - Vraťte záznamy „n“, které následují po záznamu x v seřazeném seznamu.
  5. First (n) - Vrátí první 'n' záznamy z seřazeného seznamu.
  6. Last (n) - Vrátí poslední 'n' záznamy z seřazeného seznamu.
  7. Porovnat (x, y) - Vzhledem k dvěma záznamům x a y z tabulky najděte, zda x> y.

Jednoduchá metoda, na kterou bych mohl myslet, je uložit do tabulky nějaký atribut „pozice“ a dotaz podle třídění podle tohoto atributu. V této metodě se však vkládání/úprava záznamu s hodností stává nákladnou operací. Existuje lepší metoda?

Konkrétně se chystám implementovat tabulku pomocí Amazonu SimpleDB. Užitečná by však měla být i obecná odpověď na relační databázi.

Aktualizace profilu zatížení:

Protože to plánuji pro webovou aplikaci, záleží na počtu uživatelů, kteří aplikaci používají.

Pokud jsou aktivní uživatelé 100 000 (super optimismus: P), pak by byl můj přibližný odhad za den

500k vybere, 100k vloží a odstraní, 500k aktualizace

Očekával bych, že stůl poroste celkem na 500 tisíc.

Hledám optimalizaci pro aktualizace, vkládání a operace Porovnání. Pořadí položek se bude neustále měnit a já musím tabulku aktualizovat.

44
chitti

Pokud hodnost není zcela libovolná, ale je místo toho odvozitelná od nějakého jiného majetku (např. Jména, skóre hráče atd.), Pak se dobře podívejte na Joelova odpověď .

Pokud je libovolná vlastnost vašich dat, měla by být uložena jako sloupec v tabulce záznamů. Za předpokladu, že Amazon SimpleDB je podobný typickému RDBMS, můžete tento sloupec indexovat a rychle uspokojit všechny výše uvedené dotazy pomocí vhodné strategie indexování. To je normální u RDBMS.

Vzhledem k tomu, že očekáváte vysokou aktivitu při vkládání a aktualizaci, ale také relativně vysokou aktivitu při čtení, doporučujeme provádět následující akce:

  • Seskupte tabulku do pořadí, zejména pokud je většina vašich dotazů proti hodnocení. Pokud tomu tak není, nebo pokud výběr klastrovacího klíče není v SimpleDB k dispozici, stačí vytvořit index s hodnocením jako hlavní sloupec. To by uspokojilo dotazy 3-6.
  • Index v záznamu nejprve a poté pořadí (nebo ve světě SQL Serveru stačí zaznamenat a INCLUDE- pořadí, nebo jen zaznamenat, pokud jste se seskupili do pozice) by vyhovoval dotazu 7.
  • Operace 1 a 2 lze optimalizovat řádným rozložením dat (tj. Nastavením FILLFACTOR na serveru SQL). To je obzvláště důležité, pokud se seskupujete v pořadí.
  • Při vkládání nebo aktualizaci řad udržujte co největší mezeru mezi čísly pořadí, abyste minimalizovali tuto možnost, že budete muset přehodnotit existující záznam, abyste se přizpůsobili vložení nebo aktualizaci pozice. Pokud například zařadíte své záznamy v krocích po 1000, ponecháte dostatek prostoru pro asi polovinu tolika změn a vložení s minimální šancí, že budete muset přehodnotit záznam, který se těchto změn přímo nepodílí.
  • Každou noc přehodnocujte všechny záznamy, abyste resetovali mezery mezi nimi.
  • Můžete vyladit frekvenci hromadného přepočtu a velikost mezery v pořadí tak, aby vyhovovala očekávanému počtu příloh nebo aktualizací vzhledem k počtu existujících záznamů. Pokud tedy máte 100 000 záznamů a očekáváte, že vaše přílohy a aktualizace budou 10%, ponechte dostatek místa pro 10 000 nových řad a přesměrujte každou noc.
  • Změna pořadí 500 000 záznamů je nákladná operace, ale provedené jednou denně nebo týden mimo pracovní dobu by mělo být takové databázi v pořádku. Toto hromadné přepočítávání mimo pracovní dobu, aby se zachovaly mezery v pořadí, ušetří vám to, že během normálních a špičkových hodin budete muset přehodnotit mnoho záznamů pro každou aktualizaci pozice nebo vložení.

Pokud očekáváte 100K + čtení v tabulce o velikosti 100 K +, nedoporučuji používat přístup propojeného seznamu. Na tyto velikosti se nebude dobře přizpůsobovat.

22
Nick Chammas

Obecně používám metodu „rank“, kterou popisuješ. Namísto toho, abych se pokoušel aktualizovat řádky, když bylo potřeba položky znovu uspořádat, jsem často dokázal uniknout odstraněním všech záznamů v seznamu a opětovným vložením nových položek ve správném pořadí. Tato metoda je jasně optimalizována pro vyhledávání.

Alternativním přístupem by bylo modelování záznamů jako propojeného seznamu pomocí sloupce reflexního cizího klíče „předchůdce“ v tabulce:

ID   setID   item       predecessor
---  ------  ------     ------------
1    1       Apple      null
2    1       Orange     1
3    2       Cucumber   null
4    1       Pear       2
5    1       Grape      4
6    2       Carrot     3

Můžete snadno načíst seznam a přidávat a odebírat položky s malou režií, ale dostat záznamy do správného pořadí bude složité. Možná existuje chytrý způsob, jak to udělat v jediném dotazu, pravděpodobně se spoustou aliasovaných tabulkových připojení.

Tento přístup používám často, když modeluji vztah ve stylu stromu (kategorie, složky, sady a podmnožiny). Obecně jsem měl rekurzivní funkci nějakého druhu k rekonstrukci celého stromu v mé aplikaci.

13
bpanulla

Myslím, že je třeba ložit vlastnost nebo vlastnosti, které se používají pro výpočet pořadí a poté nad nimi vytvořit index. Proč se pokusit donutit databázi fyzicky ukládat data v pořadí podle pořadí nebo pomocí ručně spravovaného propojeného seznamu, proč nenechat databázový stroj dělat to, co bylo navrženo?

6
Joel Brown

Toto jsou omezení non-RDBMS jako simpleDB. Požadované funkce nemohou být implementovány na straně DB v simpleDB, musí být implementovány z programovací strany/aplikace.

Pro RDBMS jako SQL server, funkce, které požadujete, jsou pro seskupený index základní.

  • Vložit (x) - Vložit záznam x do tabulky> Jednoduché vložení.
  • Smazat (x) - Smazat záznam x z tabulky> Jednoduché smazání.
  • Before (x, n) - Vraťte záznamy „n“ před záznamem x v seřazeném seznamu. > Vyberte nejlepší výsledky n, kde x je menší než hodnota a seřazeno podle klauzule.

  • After (x, n) - Vraťte záznamy „n“, které následují po záznamu x v seřazeném seznamu. > Vyberte nejlepší výsledky n, kde x větší než hodnota a pořadí podle klauzule.

  • First (n) - Vrátí první 'n' záznamy z seřazeného seznamu. > Vyberte nejlepší výsledky n.

  • Last (n) - Vrátí poslední 'n' záznamy z seřazeného seznamu. > Vyberte nejlepší výsledky n po objednávce podle popisu.

  • Porovnat (x, y) - Vzhledem k dvěma záznamům x a y z tabulky najděte, zda x> y. > Příkaz TSQL IF.
1
StanleyJohns

Zde je to, co jsem použil k přehodnocení své Postgres tabulky po každém vložení:

CREATE OR REPLACE FUNCTION re_rank_list() RETURNS trigger AS $re_rank_list$
DECLARE
    temprow record;
    row_idx integer := 1;    
BEGIN
    FOR temprow IN
    SELECT * FROM your_schema.your_list WHERE list_id = NEW.list_id ORDER BY rank ASC
    LOOP
        UPDATE your_schema.your_list SET rank = row_idx * 100 WHERE id = temprow.id;
        row_idx := row_idx + 1;
    END LOOP;
    RETURN NEW;
END;
$re_rank_list$ LANGUAGE plpgsql;


CREATE TRIGGER re_rank_list AFTER UPDATE ON your_schema.your_list_value
    FOR EACH ROW 
    WHEN (pg_trigger_depth() = 0)
    EXECUTE PROCEDURE re_rank_list();

Pro můj případ použití není výkon znepokojivý, ale důvěra v to, že se nikdy nezlomí nebo nebude chovat podivně, je důležitá.

0
Mark