[Mysql] Dubbio sui campi null

[Lakaj]

Ho una tabella che contiene uno user id di tipo long ed un campo di tipo binario che mi indica il tipo di user id. user id è la sola chiave
Devo esprimere delle amicizie, quindi è necessaria una associazione m a n con se stessa, che produrrebbe un'altra tabella.

Non sarebbe meglio avere una sola tabella con le colonne
uid1, uid2, tipo
impostando il tipo solo per la prima occorrenza di uid1 e per le altre occorrenze tutte a NULL e risparmiando una tabella che avrebbe l'elenco degli uid (inutile) ?
...oppure avere milioni di campi a null destabilizza lo schema logico ?
cosa conviene ? (il mio db sarà molto grande)

[gugoXX]

Io ti consiglio di separare le entita' dalle relazioni, come classicamente si insegna (e si fa)
Quindi la tabella entita' delle persone, con chiave primaria l'identificativo e tuttli gli attributi correlati (come quello dei tipi)
e una tabella per la relazione amicizia, con 2 campi che entrambi puntano all'identificativo della tabella entita', entrambi in chiave, con magari attributi relativi all'amicizia, se presenti (data del primo incontro, etc.)
Devi ancjhe chiederti come trattare la "matrice associata delle amicizie"
Se A e' amico di B, allora anche B e' amico di A? Quante entry mettiamo per questa amicizia, una oppure 2?

[Lakaj]

Originariamente inviato da gugoXX

Io ti consiglio di separare le entita' dalle relazioni, come classicamente si insegna (e si fa)
Quindi la tabella entita' delle persone, con chiave primaria l'identificativo e tuttli gli attributi correlati (come quello dei tipi)
e una tabella per la relazione amicizia, con 2 campi che entrambi puntano all'identificativo della tabella entita', entrambi in chiave, con magari attributi relativi all'amicizia, se presenti (data del primo incontro, etc.)
Devi ancjhe chiederti come trattare la "matrice associata delle amicizie"
Se A e' amico di B, allora anche B e' amico di A? Quante entry mettiamo per questa amicizia, una oppure 2?

Attenersi ad uno schema normalizzato è sempre da preferire dunque ?

ovviamente a amico di b = b amico di a
così risparmio di scrivere parecchi milioni di righe che dicono la stessa cosa

[gugoXX]

Originariamente inviato da Lakaj

Attenersi ad uno schema normalizzato è sempre da preferire dunque ?

Dipende. Normalmente si'. In questo caso direi decisamente di si'.
In prodotti commerciali solitamente si tende ad avere solo strutture normalizzate, affiancate da strutture denormalizzate che si potrebbero ricostruire da zero interrogando le strutture normalizzate, di sola lettura, per questioni di performance, e automaticamente rinfrescate quando si aggiornano le strutture normalizzate.

ovviamente a amico di b = b amico di a
così risparmio di scrivere parecchi milioni di righe che dicono la stessa cosa

Tutto sta nelle query che dovrai scrivere. Magari risparmi milioni di righe, ma puoi arrivare a perdere secondi preziosi nell'interrogazione.
Una domanda come
Chi sono tutti gli amici di 'Tizio'
Ha bisogno di una query piu' o meno complessa, a seconda di cosa avrai deciso di inserire nel database.
Prova a scriverla, e ti diro' di piu'. Posso anche sbilanciarmi a dire che per fare una cosa ben fatta e ben ottimizzata lo spazio totale speso per la soluzione simmetrica (ovvero inserire sia A-->B e B-->A) rischia di essere addirittura piu' basso che quello speso per la soluzione asimmetrica.

[banryu79]

Originariamente inviato da gugoXX

Prova a scriverla, e ti diro' di piu'. Posso anche sbilanciarmi a dire che per fare una cosa ben fatta e ben ottimizzata lo spazio totale speso per la soluzione simmetrica (ovvero inserire sia A-->B e B-->A) rischia di essere addirittura piu' basso che quello speso per la soluzione asimmetrica.

Geniale, perchè assolutamente controintuitivo, se uno ci pensa solo superficialmente.

[Lakaj]

è vero. non ci avevo pensato.
in effetti dovrei fare:

SELECT uid2 FROM Amici
WHERE uid1='uidlong'
UNION
SELECT uid1 FROM Amici
WHERE uid2='uidlong'

o qualcosa del genere, che significa interrogare 2 volte la tabella e non 1
...conviene ragionare in base a quale risorsa scarseggia di più
spazio su disco o tempo...
e anche in fase di scrittura dovrò andare a fare un controllo in più.
allora non mi conviene più
trovo interessante il discorso dei prodotti commerciali, a patto di avere molto spazio...

ps. mi fai da consulente per la tesi ?

[Lakaj]

Originariamente inviato da banryu79

Geniale, perchè assolutamente controintuitivo, se uno ci pensa solo superficialmente.

verissimo, però giuro che me ne sarei accorto, prima o dopo,perchè mi faccio troppe seghe mentali mentre scrivo codice, del resto, non avrei postato...

[gugoXX]

Originariamente inviato da Lakaj

è vero. non ci avevo pensato.
in effetti dovrei fare:

SELECT uid2 FROM Amici
WHERE uid1='uidlong'
UNION
SELECT uid1 FROM Amici
WHERE uid2='uidlong'

o qualcosa del genere, che significa interrogare 2 volte la tabella e non 1
...conviene ragionare in base a quale risorsa scarseggia di più
spazio su disco o tempo...
e anche in fase di scrittura dovrò andare a fare un controllo in più.
allora non mi conviene più
trovo interessante il discorso dei prodotti commerciali, a patto di avere molto spazio...

ps. mi fai da consulente per la tesi ?

Esatto.
Non solo il tempo e' piu' lungo, ma addirittura intendevo sbilanciarmi sul fatto che anche lo spazio risparmiato risulterebbe essere meno di quanto si pensi.

Mi spiego. Abbiamo gia' deciso che la PK della tabella debba essere composta, formata da entrambi i campi uid1 e uid2.
Per ottimizzare una query tipo

SELECT uid2 FROM Amici
WHERE uid1='uidlong'

E' bene avere un indice lungo uid1.
Ma abbiamo gia' deciso di avere la chiave primaria composta. L'inidice migliore quindi e' automatico, ed e' appunto (uid1, uid2), proprio in questo ordine.
In tal modo l'engine, per risovlere questa query, il motore andra a leggere proprio (e solo) l'indice sulla PK, scorrendo il BTree in ordine. Si chiama RangeScan.
Se la tabella dovesse occupare 20MB, ne consegue che anche questo indice qui occuperebbe proprio 20MB, essendo composto da tutte e sole le colonne della tabella in questione. Anche gli indici occupano spazio...

Ma la nostra query pero' ha anche il verso opposto. Per risolvere la WHERE uid2='12354' l'indice di prima non ci serve affatto (non e' proprio del tutto vero, Oracle per esempio potrebbe usarlo con una tecnica chiamata SkipScan, ma che e' bene usare collateralmente piuttosto che intenzionalmente)
Per poter ottimizzare tale WHERE occorre aggiungere un altro indice. l'indice con le colonne opposte, ovvero (uid2, uid1).

PS: Sarebbe quasi sufficiente anche solo un indice aggiuntivo sulla colonna uid2, ma il tempo di query ne soffrirebbe, essendo che il motore, per andare a trovare tutti i valori uid1 per il dato uid2 dovrebbe prima accedere all'indice (di nuovo Range Scan), ottenere gli indirizzi dei record che interessano, e con ciascuno di questi andare a leggere la riga corrispondente direttamente nella tabella per ottenere i valori cercati.
La soluzione ottimizzata migliore sarebbe quindi dotare la tabella proprio dell'indice aggiuntivo, (uid2,uid1), che permette la risoluzione di questa seconda parte di query di nuovo leggendo solo i dati dell'indice senza riaccedere alla tabella sottostante.
Ma cio' equivarrebbe ad aggiungere altri 20MB di spazio...

Ergo secondo me e' meglio raddoppiare la tabella rendendola simmetrica
20MB+20MB di tabella e 20MB+20MB di PK

piuttosto che tenere la soluzione asimmetrica
20MB di tabella, 20MB di PK e 20MB di indice aggiuntivo, ma con query decisamente piu' complesse, piu' difficilmente leggibili e meno performanti.
(Per fare la UNION finale il motore deve anche riordinare il risultato per prendere solo i DISTINCT, un altro O(N LOG N), dove pero' almeno sperabilmente tali risultati saranno pochi. Dipende dai dati.)

[banryu79]

Originariamente inviato da gugoXX

...snip...

Per curiosità, queste conoscence specifiche sono dovute a esperienze professionali oppure tuoi approfondimenti personali?

[gugoXX]

Beh, diciamo che e' un buon bilancio tra le due cose.
Diciamo che le aziende che ho incontrato mi hanno dato la possibilita' di approfondire questi temi sia per mia passione che per loro utilita'...
Relativamente ai Database ho lavorato in Oracle per 1 anno e mezzo, ho una certificazione Oracle e una SqlServer, ma queste certificazioni ho potuto studiarle sfruttando anche tempo aziendale, facendo domande direttamente alle fonti e soprattutto i costi delle certificazioni sono stati pagati dalle aziende stesse.
E poi tante ricerche sulle ottimizzazioni perche' i tempi delle query sono sempre lenti. Qualunque query per qualunque problema. E' una legge di Murphy.

Questo e' uno dei motivi per cui a chi mi chiede se un master dopo l'universita' vale la pena io normalmente dico di no. Secondo me e' meglio una buona azienda che da' gia' una buona impornta professionale, magari condita da esperienze come le certificazioni che le aziende stesse sono piu' che propense a stimolare. E il Master e' come se te lo ritrovassi in tasca. (almeno nel nostro campo)

[Lakaj]

Originariamente inviato da gugoXX

Esatto.
(Per fare la UNION finale il motore deve anche riordinare il risultato per prendere solo i DISTINCT, un altro O(N LOG N), dove pero' almeno sperabilmente tali risultati saranno pochi. Dipende dai dati.)

I dati potenzialmente non sono pochi, alla fine quante persone ci sono su facebook, 180 Milioni ? magari ne prendo solo un 10 milioni, che mi è finito l'hard disk,
10 milioni, in media 100 amici a persona....

p.s.: sei un Dio.

[Hiskrtapps]

però con una soluzione simmetrica in inserimento devi fare 2 insert invece che una.
se il rate di nuovi inserimenti fosse maggiore del rate di letture allora il discorso performance potrebbe cambiare.
Dipende da cosa deve fare la tua applicazione.

[Lakaj]

Originariamente inviato da Hiskrtapps

se il rate di nuovi inserimenti fosse maggiore del rate di letture allora il discorso performance potrebbe cambiare.

Ma io non conosco i tempi dell'uno o dell'altro, dovrei mettermi a fare dei benchmark.

Poi fra l'altro ho pensato che non c'è tutto questo guadagno, perchè le righe saranno la metà gestendo in modo non simmetrico.
Fare una sola select su 200 Milioni di righe o fare 2 select con una UNION su 100 Milioni di righe non è la stessa cosa ? anzi ho righe in meno...

[ho letto meglio il post in cui si parlava degli indici, non avevo capito]

[gugoXX]

Originariamente inviato da Lakaj

Ma io non conosco i tempi dell'uno o dell'altro, dovrei mettermi a fare dei benchmark.

Poi fra l'altro ho pensato che non c'è tutto questo guadagno, perchè le righe saranno la metà gestendo in modo non simmetrico.
Fare una sola select su 200 Milioni di righe o fare 2 select con una UNION su 100 Milioni di righe non è la stessa cosa ? anzi ho righe in meno...

[ho letto meglio il post in cui si parlava degli indici, non avevo capito]

No, non sarebbe la stessa cosa comunque, anche se dotassi la tabella degli indici giusti.
Questo perche' quando accedi ad una tabella via indice, sperando in un RANGE SCAN, i dati saranno pronti immediatamente dopo avere trovato il primo e l'ultimo record nell'indice, e la loro restituzione (fatta salva la lunghezza del risultato) e' praticamente gratuita.
Ma tali primo e ultimo record occorre trovarli, per ricerca tipicamente dicotomica su indice ordinato, il cui costo e' noto essere O(Log N).

Ipotizzato quindi 10.000 di record nel caso non simmetrico, avrai quindi un costo di
Log(10000) + Log(10000)

mentre nel caso simmetrico
Log(20000) e vinci comunque sempre.

Poi nel primo caso ci sarebbe anche il postprocess della UNION, che supponiamo gratuito essendo come penso molto basso il numero di record restituiti dalla query.
Altrimenti si peggiora ancora a favore della soluzione simmetrica.

[Lakaj]

Originariamente inviato da gugoXX

No, non sarebbe la stessa cosa comunque, anche se dotassi la tabella degli indici giusti.
Questo perche' quando accedi ad una tabella via indice, sperando in un RANGE SCAN, i dati saranno pronti immediatamente dopo avere trovato il primo e l'ultimo record nell'indice, e la loro restituzione (fatta salva la lunghezza del risultato) e' praticamente gratuita.
Ma tali primo e ultimo record occorre trovarli, per ricerca tipicamente dicotomica su indice ordinato, il cui costo e' noto essere O(Log N).

Ipotizzato quindi 10.000 di record nel caso non simmetrico, avrai quindi un costo di
Log(10000) + Log(10000)

mentre nel caso simmetrico
Log(20000) e vinci comunque sempre.

Poi nel primo caso ci sarebbe anche il postprocess della UNION, che supponiamo gratuito essendo come penso molto basso il numero di record restituiti dalla query.
Altrimenti si peggiora ancora a favore della soluzione simmetrica.

Morale della favola avere un solo indice su una colonna lunga n è più efficiente che avere 2 indici montati su 2 colonne diverse, ognuna lunga n/2...

Però un inserimento in più per garantire simmetria quanto mi costa ?
In simmetria avrei 2 insert subito (da parte di x) in cui dico:

x amico y
y amico x

poi però dopo arrivo a y, che ancora non sa se x l'ha messo come amico, perchè magari y è stato messo in lista dopo... quindi scatta la SELECT

quindi 2 insert + 1 select (veloce)

mentre nel caso asimmetrico avrei

1 insert + 1 select (lenta)

Ma questa insert in più che prestazioni ha ?
io sapevo che le scritture erano più lente delle letture, del resto comportano un aggiornamento degli indici...

[CozzaAmara]

Originariamente inviato da Lakaj

Attenersi ad uno schema normalizzato è sempre da preferire dunque ?

No, la normalizzazione è la retta via, nonostante ciò si deve essere consapevoli di quando si può / si vuole piegare o violare le regole.

Una base dati totalmente priva di ridondanze non esiste, esistono però DB progettati bene e DB progettati male, dipende molto dal caso specifico.

ovviamente a amico di b = b amico di a
così risparmio di scrivere parecchi milioni di righe che dicono la stessa cosa

Questo ovviamente è un bene, se ritieni di dover lavorare con volumi di dati molto grandi, meglio spendere un pò più di tempo nella normalizzazione e nello sviluppo del software piuttosto che dover piangere lacrime e sangue in un secondo momento.

[Lakaj]

Originariamente inviato da CozzaAmara

Questo ovviamente è un bene, se ritieni di dover lavorare con volumi di dati molto grandi, meglio spendere un pò più di tempo nella normalizzazione e nello sviluppo del software piuttosto che dover piangere lacrime e sangue in un secondo momento.

Invece penso che ricorro alla soluzione simmetrica. Ha ragione gugo.
...in fondo lo spazio non è un bene che scarseggia nel 2009, il tempo si.
meglio qualche giga in più, purchè la cosa non sia esponenziale...

[gugoXX]

Originariamente inviato da Lakaj

Invece penso che ricorro alla soluzione simmetrica. Ha ragione gugo.
...in fondo lo spazio non è un bene che scarseggia nel 2009, il tempo si.
meglio qualche giga in più, purchè la cosa non sia esponenziale...

Esponenziale no, al massimo raddoppia (Polinomiale)
Le insert non pensano tanto fino a che non si giunge a qualche centinaia di milione di record, e comunque normalmente le ottimizzazioni sono piu' sulle letture (presumibilmente tante) che sulle scritture (poche).
Certo che se inserisci solo e non leggi mai, come nei DB di log, allora le scritture diventano importanti.

Originariamente inviato da cozzaAmara

No, la normalizzazione è la retta via,

Confermo il discorso.