Att uppskatta selektiviteten hos en fråga är ett viktigt steg i nästan alla kostnadsbaserade frågeoptimerare. De flesta av dagens databaser bygger på histogram eller prover som regelbundet uppdateras genom att återscanna data som de underliggande data förändringar. Eftersom det är kostsamt att göra regelbundna avsökningar, är denna statistik ofta gammalmodig och leder till dåliga skattningar av selektiviteten. Som ett alternativ till skanningar har man föreslagit frågedrivna histogram, som förfinar histogrammen baserat på de faktiska urvalen av de observerade frågorna. Tyvärr är dessa metoder antingen alltför dyra att använda i praktiken-dvs., kräver ett exponentiellt antal hinkar-eller snabbt förlora sin fördel som de observerar fler frågor. Till exempel, den senaste tekniken kräver 318.936 hinkar (och över 8 sekunder av förfining overhead per fråga) efter att ha observerat endast 300 frågor. I detta dokument föreslår vi en selektiv inlärningsram, kallad QuickSel, som hamnar i det frågedrivna paradigmet men inte använder histogram. Istället bygger den en intern modell av de underliggande data, som kan förfinas betydligt snabbare (t.ex. endast 1,9 millisekunder för 300 frågor). Denna snabba förfining gör det möjligt för QuickSel att kontinuerligt lära sig från varje fråga och ge allt mer exakta selektivitetsuppskattningar över tid. Till skillnad från frågedrivna histogram förlitar sig QuickSel på en blandningsmodell och en ny optimeringsalgoritm för att träna sin modell. Våra omfattande experiment på två verkliga datauppsättningar bekräftar att, med tanke på samma målnoggrannhet, är QuickSel i genomsnitt 254,6× snabbare än toppmoderna frågedrivna histogram, inklusive ISOMER och STHoles. Med tanke på samma rymdbudget är QuickSel dessutom i genomsnitt 57,3% och 91,1% mer exakt än periodiskt uppdaterade histogram respektive prover.
QuickSel erbjuds med hjälp av frågedrivna blandningsmodeller som ett alternativ till att använda histogram och prover för adaptiv selektivitet lärande REF.
QuickSel: Quick Selectivity Learning with Mixture Models
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science']}