Evaluation of skyline algorithms in PostgreSQL

ABSTRACT

In this paper, we present our work on evaluating the skyline algorithms BNL, SFS, and a variant of LESS in PostgreSQL. It is well known that the performance of skyline queries is sensitive to a number of parameters. From extensive experiments on skyline implementations we have discovered several rules, which are remarkably simple and useful, but hard to obtain from theoretical investigation. Our findings are beneficial for developing heuristics for the skyline query optimization, and in the meantime, provide some insight for a deeper understanding of the skyline query characteristics.

REFERENCES

• 1: S. Börzsönyi, D. Kossmann, and K. Stocker. The skyline operator. In 17th International Conference on Data Engineering (ICDE' 01), pages 421--432, Heidelberg, Germany, 2001. IEEE.
• 2: S. Chaudhuri, N. Dalvi, and R. Kaushik. Robust cardinality and cost estimation for skyline operator. In ICDE '06: Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), page 64, Washington, DC, USA, 2006. IEEE Computer Society.
• 3: J. Chomicki, P. Godfrey, J. Gryz, and D. Liang. Skyline with presorting. In U. Dayal, K. Ramamritham, and T. M. Vijayaraman, editors, ICDE, pages 717--816. IEEE Computer Society, 2003.
• 4: H. Eder. Random dataset generator for skyline operator evaluation. http://randdataset.projects.postgresql.org/, 2007.
• 5: P. Godfrey, R. Shipley, and J. Gryz. Maximal vector computation in large data sets. In K. Böhm, C. S. Jensen, L. M. Haas, M. L. Kersten, P.-Å. Larson, and B. C. Ooi, editors, VLDB, pages 229--240. ACM, 2005.
• 6: P. Godfrey, R. Shipley, and J. Gryz. Algorithms and analyses for maximal vector computation. VLDB J., 16(1):5--28, 2007.
• 7: D. Kossmann, F. Ramsak, and S. Rost. Shooting stars in the sky: An online algorithm for skyline queries. In VLDB, pages 275--286. Morgan Kaufmann, 2002.
• 8: D. Papadias, Y. Tao, G. Fu, and B. Seeger. An optimal and progressive algorithm for skyline queries. In A. Y. Halevy, Z. G. Ives, and A. Doan, editors, SIGMOD Conference, pages 467--478. ACM, 2003.
• 9: D. Papadias, Y. Tao, G. Fu, and B. Seeger. Progressive skyline computation in database systems. ACM Trans. Database Syst., 30(1):41--82, 2005.
• 10: K.-L. Tan, P.-K. Eng, and B. C. Ooi. Efficient progressive skyline computation. In P. M. G. Apers, P. Atzeni, S. Ceri, S. Paraboschi, K. Ramamohanarao, and R. T. Snodgrass, editors, VLDB, pages 301--310. Morgan Kaufmann, 2001.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Performance

Keywords:
PostgreSQL, skyline