Filtered statistics

ABSTRACT

Column statistics are an important element of cardinality estimation frameworks. More accurate estimates allow the optimizer of a RDBMS to generate better plans and improve the overall system's efficiency. This paper introduces filtered statistics, which model value distribution over a set of rows restricted by a predicate. This feature, available in Microsoft SQL Server, can be used to handle column correlation, as well as focus on interesting data ranges. In particular, it fits well for scenarios with logical subtables, like flexible schema or multi-tenant applications. Integration with the existing cardinality estimation infrastructure is presented.

REFERENCES

• 1: Srini Acharya , Peter Carlin , Cesar Galindo-Legaria , Krzysztof Kozielczyk , Pawel Terlecki , Peter Zabback, Relational support for flexible schema scenarios, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454169]
• 2: Stefan Aulbach , Torsten Grust , Dean Jacobs , Alfons Kemper , Jan Rittinger, Multi-tenant databases for software as a service: schema-mapping techniques, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376736]
• 3: Srini Acharya , Cesar Galindo-Legaria , Milind Joshi , Babu Krishnaswamy , Stefano Stefani , Pawel Terlecki, Filtered Indices and Their Use in Flexible Schema Scenarios, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1259-1266, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497535]
• 4: Ihab F. Ilyas , Volker Markl , Peter Haas , Paul Brown , Ashraf Aboulnaga, CORDS: automatic discovery of correlations and soft functional dependencies, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007641]
• 5: Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
• 6: V. Markl , P. J. Haas , M. Kutsch , N. Megiddo , U. Srivastava , T. M. Tran, Consistent selectivity estimation via maximum entropy, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.1, p.55-76, January 2007 [doi>10.1007/s00778-006-0030-1]
• 7: Nicolas Bruno , Surajit Chaudhuri, Conditional selectivity for statistics on query expressions, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007604]
• 8: Alantha Newman, The Maximum Acyclic Subgraph Problem and Degree-3 Graphs, Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems and 5th International Workshop on Randomization and Approximation Techniques in Computer Science: Approximation, Randomization and Combinatorial Optimization, p.147-158, August 18-20, 2001
• 9: Arnd Christian König , Gerhard Weikum, A Framework for the Physical Design Problem for Data Synopses, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.627-645, March 25-27, 2002
• 10: César A. Galindo-Legaria , Milind M. Joshi , Florian Waas , Ming-Chuan Wu, Statistics on views, Proceedings of the 29th international conference on Very large data bases, p.952-962, September 09-12, 2003, Berlin, Germany
• 11: Nicolas Bruno , Surajit Chaudhuri, Exploiting statistics on query expressions for optimization, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564722]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms

Keywords:
cardinality estimation, conditional data distribution, flexible schema, multi-tenant application