I arbejdet med databasen til QuestGame har vi valgt PostgreSQL med PostGIS, fordi spillet anvender geografiske lokationer. Hvert QuestItem har en Location, som gemmes som geografiske koordinater, og disse positioner bruges af mobilapplikationen til at placere QuestItems på kortet og afgøre, hvornår spilleren nærmer sig dem.
I forbindelse med opsætningen af PostGIS begyndte jeg også at undersøge GiST-indekser. Et GiST-indeks bruges blandt andet til at optimere spatiale forespørgsler, og umiddelbart virkede det derfor som en oplagt del af vores databaseopsætning. Når vi allerede anvender geografiske datatyper, virkede det naturligt også at indeksere dem på en måde, der er udviklet til geografiske søgninger.
Efterhånden som jeg undersøgte emnet nærmere, blev det dog tydeligt, at spørgsmålet ikke blot var, om GiST er velegnet til geografiske data, men om vores konkrete use cases faktisk har behov for det.
Hvordan bruges geografien i QuestGame?
QuestGame er i sin nuværende form ikke bygget som et åbent spil, hvor en spiller åbner applikationen og søger efter Quests i nærheden.
En spiller deltager i stedet i en bestemt QuestSession, eksempelvis ved hjælp af en spilkode eller invitation. Når spilleren er kommet ind i sessionen, hentes de relevante QuestItems til klienten. Dette kan gøres med en Projection, så klienten kun modtager de oplysninger, den har behov for.
Det betyder, at klienten allerede kender de relevante QuestItems og deres geografiske placeringer.
Spilmotoren kan derefter løbende sammenligne spillerens GPS-position med QuestItems placeringer og bruge denne information til brugeroplevelsen. Et QuestItem kan eksempelvis begynde at lyse op eller på anden måde indikere, at spilleren er kommet tæt nok på.
Når spilleren forsøger at åbne et bestemt QuestItem, skal serveren foretage den egentlige validering. Klienten sender spillerens aktuelle position samt det konkrete QuestSessionItem, som forsøges åbnet. Backend anvender derefter PostGIS til at kontrollere afstanden mellem spillerens position og den gemte QuestSessionLocation.
Her kan en funktion som ST_DWithin bruges til at afgøre, om spilleren befinder sig inden for den tilladte aktiveringsradius.
Det geografiske spørgsmål kan eksempelvis være:
Er Player højst 25 meter fra QuestSessionItem #42?Code language: CSS (css)PostGIS foretager den geografiske beregning, mens backend anvender resultatet som en del af forretningslogikken og afgør, om QuestSessionItem må åbnes.
Hvor passer GiST ind?
Det var her, min oprindelige forståelse af GiST skulle nuanceres.
Et GiST-indeks er særligt nyttigt, når databasen selv skal finde geografiske kandidater blandt mange rækker.
Det kunne eksempelvis være en forespørgsel som:
Find alle Quests inden for fem kilometer fra spilleren.Her ved databasen ikke på forhånd, hvilke rækker der er relevante. Hvis der findes meget store mængder geografiske data, vil det være ineffektivt at beregne afstanden mellem spillerens position og samtlige punkter i databasen.
Et spatialt GiST-indeks gør det muligt først at indsnævre søgningen til geografisk relevante kandidater. PostGIS kan derefter foretage den præcise kontrol på den mindre mængde data.
I vores nuværende valideringsflow er situationen anderledes.
Når spilleren forsøger at åbne et QuestSessionItem, kender systemet allerede det konkrete ID. Databasen behøver derfor ikke spørge:
Hvilke QuestItems ligger i nærheden?Den skal kun spørge:
Hvor langt er spilleren fra dette ene QuestSessionItem?Dermed er kandidatfeltet allerede reduceret til én række, inden den geografiske beregning foretages.
GiST-indekset bidrager derfor ikke med nogen væsentlig optimering i denne use case.
En løsning på et problem vi ikke har endnu
Denne erkendelse ændrede min vurdering af GiST i projektet.
Teknologien er relevant for PostGIS, men det betyder ikke automatisk, at den er relevant for netop vores projekt, selvom det arbejder med geografiske data. Et indeks bør vælges på baggrund af de forespørgsler, systemet faktisk udfører.
I QuestGame bliver de relevante QuestItems allerede udvalgt som følge af spillerens deltagelse i en QuestSession. Klienten står derefter for den løbende afstandsberegning til brugeroplevelsen, mens backend og PostGIS foretager en server-side kontrol, når et konkret QuestSessionItem forsøges åbnet.
Der er derfor ikke behov for at bruge databasen som geografisk søgemaskine i vores MVP.
Det betyder samtidig, at det vil være misvisende at begrunde et GiST-indeks med, at det gør den nuværende afstandsvalidering hurtigere. Den geografiske beregning foretages kun mellem to kendte punkter, og et spatialt indeks har meget lidt at bidrage med i den situation.
En mulig fremtidig discover-feature
GiST kan dog blive relevant, hvis QuestGame senere ændrer karakter.
En mulig videreudvikling kunne være at gøre nogle Quests offentligt tilgængelige og lade spillere opdage spil i nærheden af deres aktuelle position.
Applikationen kunne eksempelvis tilbyde:
Find offentlige Quests inden for 10 kilometer.Her vil databasen pludselig skulle foretage en egentlig spatial søgning blandt mange forskellige Quests eller QuestItems.
Hvis Quest på dette tidspunkt får sin egen Location, eksempelvis en startposition eller et geografisk centrum, kunne PostGIS søge direkte blandt offentlige Quests.
Alternativt kunne en Quest findes på baggrund af placeringen af dens QuestItems.
I begge tilfælde vil et GiST-indeks være langt mere relevant, fordi databasen skal finde geografiske kandidater frem for blot at kontrollere én allerede kendt position.
Jeg vil derfor stadig klargøre datalaget til denne mulighed. Vi anvender allerede PostGIS og geografiske datatyper, og det er forholdsvis enkelt at beholde understøttelsen af et spatialt indeks. Det giver lidt ekstra lagerforbrug og vedligeholdelse ved ændringer i de indekserede data, men for vores nuværende datamængder er dette begrænset.
Dermed kan en senere discover-feature implementeres uden først at skulle ændre fundamentet for håndteringen af geografiske data.
Konklusion
Min undersøgelse af GiST begyndte med en antagelse om, at spatialt indeks og PostGIS naturligt hørte sammen i QuestGame.
Efter at have analyseret vores konkrete dataflow og use cases er min konklusion mere nuanceret.
GiST er en relevant teknologi til geografiske søgninger, men vores MVP udfører ikke den type forespørgsler, hvor indekset giver en væsentlig fordel. De relevante QuestItems er allerede kendt af klienten, og når backend foretager positionsvalidering, sker det mod ét bestemt QuestSessionItem.
GiST er derfor ikke nødvendigt for den funktionalitet, vi aktuelt har planlagt.
Jeg vælger alligevel at klargøre datalaget til spatial indeksering, fordi det giver en forholdsvis billig mulighed for senere at udvide QuestGame med eksempelvis offentlige Quests og en geografisk discover-feature. Dette har vores “kunde” italesat som en reel mulighed i nærmeste fremtid, derfor har jeg valgt at forberede systemet til dette.
Den vigtigste læring har derfor ikke været, hvordan man tilføjer et GiST-indeks, men hvornår et sådant indeks faktisk løser et problem. Et databaseindeks bør ikke vælges alene ud fra den datatype, der anvendes, men ud fra de forespørgsler og adgangsmønstre systemet skal understøtte.
