Een soort van relevance ranking

[Kalentum]

Ik kreeg vandaag een verzoekje waar ik niet direct uitkwam. Ik heb een database met personen die voor bepaalde periodes ingezet kunnen worden op projecten. Het gaat om ontwikkelingswerk maar voor de discussie is het handiger om auto's als voorbeeld te nemen, bv een autosite. Ik heb even gekozen voor vrij simpele kenmerken (waar geen verloop in zit, bv niet voor bouwjaar of km stand ofzo)

Van een auto worden de volgende gegevens vastgelegd:

• Type brandstof (diesel, benzine, LPG)
• Transmissie (automaat, handgeschakeld)
• Kleur (rood,groen,blauw,wit,grijs,zwart)
• Merk (ford,mazda,opel, renault)
• Model (hatchback,station, sedan)

Meer is er niet bekend van een auto.

De site krijgt een zoekfunctie waarin op 1 of meer kenmerken kan worden gezocht. Normaal gesproken zou dit een lijstje opleveren van auto's die aan alle kenmerken voldoen. Maar nu ligt er een verzoek of het mogelijk is om te sorteren op relevantie waarbij geldt dat hoe meer een auto past, hoe relevanter het wordt. Zoek je dus op alle 5 kenmerken dan komen de auto's die aan alle kenmerken voldoen eerst, dan die aan 4 kenmerken voldoen, dan aan 3 kenmerken etcetera.

Het idee hierachter is dat als een perfecte match niet bestaat, er toch nog resultaten komen die minder perfect zijn.

De applicatie is geschreven in PHP en draait op een MySQL database (5.0).

Mijn eerste ingeving was om voor elk kenmerk een query te doen en dan iedere keer het resultaat door te lopen om dan te kijken welke auto's matchen met hoeveel kenmerken en dat dan op te slaan. Dit is echter een oplossing die veel te traag is (het gaat momenteel om 900 records).

Wat misschien een haalbare optie is: een tabel met structuur:
car_id, key, value
bv:
1, merk, ford
1, kleur, zwart
1, brandstof, diesel
2, merk, renault
2, brandstof, LPG
2, kleur, grijs
3, merk, ford,
3, kleur, wit,
3, brandstof, LPG
....

Zoeken op 'brandstof = LPG' wordt dan iets als:

code:

SELECT car_id, count(*) FROM tabel WHERE key = brandstof AND value = LPG GROUP BY car_id ORDER BY count(*)

Nadeel van deze aanpak is dat ik een aparte tabel moet bijhouden met zoekvelden, nu staan die waarden nog mooi bij elkaar in 1 tabel.

Heeft iemand nog andere idee-en? Of is mijn aanpak the way to go?

[LauPro]

Toevallig ben ik met eenzelfde systeem bezig. Waarbij er dus een matching plaats moet vinden op een 5tal kenmerken met daarbij resultaten die 100% matchen, 80%, 60% etc. Gekozen in de huidige opzet zijn een aantal staffels dus. Een match die op 5 kenmerken matched is dus 100%, een match op 4 kenmerken 80%.

De query hiervoor is vrij lang. Het komt er op neer dat een 5tal queries met een aantal UNION's uiteindelijk 1 grote resultset maken. En ik moet zeggen dat het systeem (met de juiste indexes) vrij snel is, en dan heb ik het getest met ongeveer 10.000 objecten. De totale parsetime incl DB-time bleef onder de 100ms die ik hanteer.

Andere opties zijn volgens mij dat je door middel van triggers of SP's bepaalde scores genereert welke je dan gebruikt in je query bij de zoekopdracht. Dit vond echter minder elegant.

Wat echter wel belangrijk is dat het systeem op dit moment dus geen rekening houdt met 'noncombinaties'. In jouw geval zou je bijvoorbeeld nooit de combinatie kunnen hebben waarbij merk x LPG motor levert, omdat die er gewoon niet zijn. Dit zou je eigenlijk mee moeten wegen in je scoremodel. Omdat als je dus bijvoorbeeld per se diesel wil, dan vallen eigenlijk al alle LPG en benzine auto's of.

Dus naast de staffel zul je ook een priorisatie in de kenmerken toe moeten passen. Bepaalde kenmerken hebben meer waarden dan anderen.

[eamelink]

Wat ik doe in zulke gevallen is meestal een temporary table maken, en die vullen met resultaten. Je maakt een temporary table met velden 'id' en 'score'. Vervolgens doe je losse zoekqueries, en de resultaten daarvan laat je in de temporary tabel zetten en daarbij de score te verhogen.

Je krijgt dan zoiets :

SQL:

CREATE TEMPORARY TABLE search (id INT, score INT DEFAULT 1, PRIMARY KEY (id))

En vervolgens heb je je gewone (simpele) searchqueries :

SQL:

SELECT id FROM cars WHERE brandstof like 'kerosine'

Maar die gebruik je als subquery in een insert in je temporary table:

SQL:

INSERT into usersearch (id) {select} ON DUPLICATE KEY UPDATE score = score + 1

Waarbij {select} dus die query ervoor is

Aan het einde kan je dan gewoon je zoektabel selecteren, sorteren op score, delen door maxscore (moet je zelf even bijhouden), vermenigvuldigen met 100% en je normale tabel eraan joinen

SQL:

SELECT (score / {maxscore} * 100) as match_percentage, cars.* 
FROM search 
LEFT JOIN cars  
ON cars.id = search.id 
ORDER BY score 
LIMIT 10

[ Voor 7% gewijzigd door eamelink op 19-09-2007 19:18 ]

[MrBucket]

Ik heb zelf meer ervaring met MS SQL Server, maar ik zie dat je in MySql ook de beschikking hebt over user-defined functions (in MySql-termen: een stored routine die een scalar teruggeeft).

Het zou nl. mogelijk moeten zijn om een functie te schrijven die voor een enkele carID de ranking bepaalt. Deze functie krijgt dan als argumenten de zoekcriteria (e.g. diesel, automaat, rood, ...) en een carID waarvoor de ranking moet worden bepaald:

(pseudo-code, '@' wordt gebruikt om variabelen en parameters mee aan te duiden) :

SQL:

create function dbo.udf_calcRanking(
  @carID int,
  @req_fuelID int,
  @req_transmissionID int,
  @req_colorID int)
returns int
as begin
-- Haal brandstof, schakeling en kleur op voor de auto met de gegeven carID
declare @found_fuelID int, @found_transmissionID int, @found_colorID int
select 
   @found_fuelID = fuel.fuelID,
   @found_transmissionID = transmission.transID,
   @found_colorID = color.colorID
from
  <....>
where car.carID = @carID

-- Bepaal ranking
declare @ranking int
set @ranking = 0

if @found_fuelID = @req_fuelID then
  set @ranking = @ranking + 1
if @found_transmissionID = @req_transmissionID then
  set @ranking = @ranking + 1
if @found_colorID = @req_colorID then
  set @ranking = @ranking + 1

return @ranking
end

Zo'n functie kun je dan rechtstreeks in je query gebruiken:

SQL:

select 
  car.carID,
  dbo.udf_calcRanking(
    car.carID, 
    1,  -- Fuel = diesel,
    1,  -- Transmission = automatic,
    3   -- Color = red)
from car
order by dbo.udf_calcRanking(car.carID, 1, 1, 3) desc

(ik geloof dat aliasing niet mogelijk is bij een order by?)

[Kalentum]

Bedankt voor het meedenken en het aandragen van alternatieve oplossingen.

Jullie dragen allemaal oplossingen aan waarin de relevantiescore ook wordt berekend. Daar had ik nog niet aan gedacht. In principe is het allemaal nogal simpel: voor elk kenmerk dat matcht krijg je score 1. Maximum score is dus het aantal kenmerken waarop is gezocht. Bij zoeken op 1 kenmerk is het dus 100% of niets. Bij zoeken op 2 kenmerken 100,50 of 0 enz.

Ik denk dat die union aanpak het beste gaat werken. Ik hoop dat het niet een te erge aanslag op de performance is (de applicatie beschikt over een nogal gecompliceerd authorisatiesysteem wat complexe SQL statements oplevert).

Die stored procedure heeft als nadeel dat je de database gaat gebruiken voor logica die in de applicatie thuishoort. Als het aantal zoekvelden wijzigt moet ik die procedure aanpassen. Het kan net zo goed in de applicatie

[ Voor 5% gewijzigd door Kalentum op 20-09-2007 10:19 ]

[Verwijderd]

volgens mij gaat een combinatie tussen een handjevol OR clauses en een Count op het resultaat sneller dan dan unions of andere vormen van sub-queries.

SQL:

select
   count(*) * 20
from
   auto,
   eigenschap_1,
   eigenschap_2
where 
   (eigenschap_1.id = auto.id and eigenschap_1.kleur = 'rood')
   or
   (eigenschap_2.id = auto.id and eigenschap_2.brandstof = 'benzine')

[ Voor 11% gewijzigd door Verwijderd op 20-09-2007 10:54 ]

[Kalentum]

Absoluut. Maar de gegevens staan nu in 1 tabel dus dan kun je beter een UNION doen en dan daar de count overheen doen. De tabelstructuur die ik eerst had bedacht (met een propertytabel) heb ik losgelaten.