Top-k queries

to_be_sorted =[]
for tuple in R:
	# compute S for each tuple
	to_be_sorted.append({tuple,S(tuple)})

# sort based on S value and return the first k values
return to_be_sorted.sort().head(k)

❗ questo approccio e estremamente costoso in quanto prevede il
href="/tecnologie_basi_dati/sorting">sorting di tutte le tuple, ancora peggio se la query prevede uno o più join

Inoltre si possono verificare casi di near miss o information overload, per esempio le query

SELECT * FROM  UsedCarsTable
WHERE Vehicle = ‘Audi/A4’ AND Price <= 21000
ORDER BY 0.8*Price + 0.2*Mileage

SELECT * FROM UsedCarsTable
WHERE Vehicle = ‘Audi/A4’
ORDER BY 0.8*Price + 0.2*Mileage

soffrono rispettivamente di escludere elementi con prezzo di poco maggiore ma un numero di chilometri estremamente basso (near-miss) e l’altra di dare in output tutti i veicoli di un dato modello (information overload)

Valutazione di una query top-$k$
#

Per la valutazione e necessario considerare due aspetti principali:

numero di relazioni da accedere, valori aggregati
modalità di accesso ai dati (indici in qualche attributo di ranking)

prendendo come riferimento la forma più semplice di query top-$k$

SELECT <some attributes>
FROM R
WHERE <Boolean conditions>
ORDER BY S(<some attributes>)
STOP AFTER k

E necessario estendere l’algebra relazionale con un operatore $\tau_{k,S}$ che restituisca le $k$ tuple migliori secondo la funzione di scoring $S$

flowchart TD top_operator --> filter --> Relation_R

Implementazione dell’operatore top $\tau_{k,s}$
#

L’operatore top può essere implementato in due modalità

top-scan la stream di tuple in ingresso e già ordinata e di conseguenza e sufficiente fornire in output le prime $k$ tuple

💡 Tip

questo operatore puo lavorare in pipeline

top-sort la stream non e ordinata e l’operatore la deve ordinare per poi fornire le tuple in output

❗ questa implementazione non può lavorare in
href="/tecnologie_basi_dati/ottimizzazione_interrogazioni#implementare-lesecuzione-in-pipeline-interfaccia-a-iteratore">pipeline in quanto necessita di fare sorting

top-sort operator
#

Per implementare l’operatore top-sort e sufficiente allocare un buffer $B$ che contenga le $k$ tuple, ad ogni tupla letta la si confronta con la $k$-esima già nel buffer e la si scarta se non maggiore

ℹ️ se una tupla non e maggiore dell’ultima migliore $k$-esima si presume non fara parte del risultato finale

Query top-$k$ multidimensionali
#

Le query top-$k$ coinvolgono spesso più di un attributo nella funzione di scoring $S$

SELECT *
FROM USEDCARS
WHERE Vehicle = 'Audi/A4'
ORDER BY 0.8*Price + 0.2*Mileage
STOP AFTER 5;

In questo caso la situazione e più complessa:

se non si ha nessun indice non c’e’ altra soluzione che applicare l’operatore di top-sort
Se si può sfruttare un indice sull’attributo di selezione (clausola WHERE) allora la situazione migliora ma dipende dalla selettività della selezione

❗ senza selezione si sta nella merda….

Cosa possiamo fare se avessimo un indice sugli attributi di ranking?, come dovrebbe essere l’indice?

analizziamo la geometria :)

Se si plottano le tuple in un grafo basato sugli attributi di scoring si ottiene che le tuple che soddisfano la top-$k$ query si trovano tutte sotto una data linea

si considera di cercare macchine con i parametri di scoring più bassi possibili

Si può generalizzare a un punto qualunque dello spazio $q$, in questo caso si ottiene che i punti che soddisfano la top-$k$ query sono quelli all’interno di una regione di spazio intorno al punto di query $q$

Di conseguenza il problema delle top-$k$ query si riduce al problema di trovare i $k$ nearest neighbors rispetto al query point $q$

top-$k$ query come problemi di $k$-NN
#

Di conseguenza il problema può essere modellato come segue, dato il seguente modello

uno spazio $D$-dimensionale formato dagli attributi di scoring $A = (A_1,A_2,...,A_D)$
una relazione $R(A_1,A_2,...,R_1,R_2,....)$
un query point $q = (q_1,q_2,..,q_D)$
una funzione $d: A \times A \rightarrow \Re$ che misura la distanza fra due punti di $A$

Il problema diventa:

dati un punto $q$ una relazione $R$, un intero $k \geq 1$ e una funzione distanza $d$ determinare le $k$ tuple in $R$ che sono le più vicine a $q$ secondo $d$

Risolvere query top-$k$ con indici
#

Una possibilità per risolvere le query top-$k$ e quello di usare b+tree multiattributo , questa soluzione non e ottimale. e molto meglio usare indici multidimensionali come i r-tree

ℹ️ i b+tree multi-attributo mostrano gli stessi problemi che si hanno in caso di
href="/tecnologie_basi_dati/indici_multidimensionali#limiti-del-b+tree">window query

Determinare se un nodo contiene foglie utili: $d_{MIN}$ limite
#

Per determinare se un nodo dell’albero deve essere considerato in fase di ricerca si definisce la distanza del nodo come la distanza della foglia più vicina al punto di ricerca $q$

$$ d_{MIN}(q,Reg(N)) = inf\{d(q,p) | P \in Reg(N)\} $$

Di conseguenza si ha che se il nodo $N$ contiene punti interessanti deve essere vero che $d_{MIN}$ deve essere inferiore del raggio di ricerca $r$

$$ Reg(q) \cap Reg(N) \neq \emptyset \Leftrightarrow d_{MIN}(q,Reg(N)) \leq r $$

Risolvere le query top-$k$: algoritmo knnoptimal
#

Per risolvere le query con il modello sopracitato si introduce l’algoritmo KNNOptimal, l’algoritmo scandisce l’albero considerando i nodi $d_{MIN}(q,Reg(N)) < r$ e memorizza la tupla $t$ con $d(q,t)$ minore

# query point input
q = {}

# Initialize pq with [ptr(rn),0];
PQ = []
PQ.append({ptr(RN),0})
rNN = 10000000;
while PQ.len() != 0:
	N = get_distance_and_point(PQ.pop())
	# read page from disk
	Read(N)
	if N is leaf:
		for t in N:
			if d(q,t) < rNN:

				# save tuple for result
				result = t
				# update search radius
				rNN = d(q,t)
				# update queue
				update(PQ)
	else:
		for Nc in N:
			if dMIN(q,Reg(Nc)) < rNN:
				ENQUEUE(PQ,[ptr(Nc), dMIN(q,Reg(Nc))])
return result, rNN

L’algoritmo KNNOptimal e corretto e I/O-ottimale in quanto accede solo pagine in cui e possibile trovare foglie vicine al risultato

Knnoptimal e query top-$k$ con filtro
#

In caso di query della forma

SELECT *
FROM USEDCARS
WHERE Vehicle = 'Audi/A4'
ORDER BY 0.8*Price + 0.2*Mileage
STOP AFTER 5;

Non e detto che l’algoritmo KNNOptimal restituisca tuple concordi con il parametro di filtering, per supportare la casistica si utilizza una variante del KNNOptimal con supporto al distance browsing

Nella coda PQ si includono anche le tuple e l’algoritmo termina quando il primo elemento della coda e una tupla