Enabling Cost-based Optimization for Top-k Queries- A Unified .pptVIP

Supporting Ad-Hoc Ranking Aggregates Chengkai Li (UIUC) joint work with Kevin Chang (UIUC) Ihab Ilyas (Waterloo) Ranking (Top-k) Queries Find the top k answers with respect to a ranking function, which often is the aggregation of multiple criteria. Ranking is important in many database applications: E-Commerce Find the best hotel deals by price, distance, etc. Multimedia Databases Find the most similar images by color, shape, texture, etc. Search Engine Find the most relevant records/documents/pages. OLAP, Decision Support Find the top profitable customers to send ads. RankSQL: a RDBMS with Efficient Support of Ranking Queries Rank-Aware Query Operators [SIGMOD02, VLDB03] Algebraic Foundation and Optimization Framework [SIGMOD04, SIGMOD05] SPJ queries (SELECT … FROM … WHERE … ORDER BY …) Ad-Hoc Ranking Aggregate Queries [SIGMOD06] top k groups instead of tuples. (SELECT … FROM … WHERE … GROUP BY … ORDER BY …) Example 1: Advertising an insurance product What are the top 5 areas to advertise a new insurance product? SELECT zipcode, AVG(income*w1+age*w2+credit*w3) as score FROM customer WHERE occupation=‘student’ GROUP BY zipcode ORDER BY score LIMIT 5 Example 2: Finding the most profitable combinations What are the 5 most profitable pairs of (product category, sales area)? SELECT P.cateogy, S.zipcode, MID_SUM(S.price - P.manufact_price) as score FROM products P, sales S WHERE P.p_key=S.p_key GROUP BY P.category, S.zipcode ORDER BY score LIMIT 5 Ad-Hoc Ranking Ranking Condition : F=G(T) e.g. AVG (income*w1+age*w2+credit*w3) MID_SUM (S.price - P.manufact_price) G: group-aggregate function Standard (e.g., sum, avg) User-defined (e.g., mid_sum) T: tuple-aggregate function arbitrary expression e.g., AVG (income*w1+age*w2+credit*w3), w1, w2, w3 can be any values. W