Your browser does not support JavaScript!
http://iet.metastore.ingenta.com
1887

access icon openaccess Adaptive indexing approach for main memory column store

This is an open access article published by the IET under the Creative Commons Attribution License (http://creativecommons.org/licenses/by/3.0/)
Received 20/03/2016, Accepted 29/06/2016, Published 14/07/2016

Owing to efficient query processing for random workload, the hybrid crack sort (HCS) has become an important adaptive indexing approach in main-memory column store. However, under sequential workload scenarios, the HCS does not obtain a good query execution performance, because of great reorganisation overhead imposed on the initial queries. The authors propose a hybrid radix crack sort (HRCS) approach to solve this problem. By the adoption of radix-based partition strategy, it divides the unsorted column into disjoint key ranges and then conducts data reorganisation in at most two key ranges for each query. For HRCS, only a small portion of the whole column needs to be touched for the processing of each query, thus reducing the reorganisation cost and improving the query execution performance. The final experiments show that the novel HRCS approach can obtain a higher query execution performance for not only random workload but also sequential workload, as compared with HCS.

Inspec keywords: sorting; storage management; query processing; database indexing

Other keywords: hybrid radix crack sort approach; reorganisation overhead; adaptive indexing approach; query processing; HCS; HRCS approach; query execution performance improvement; disjoint key ranges; unsorted column; reorganisation cost reduction; random workload; sequential workload scenarios; data reorganisation; main-memory column store; radix-based partition strategy; hybrid crack sort

Subjects: File organisation; Database management systems (DBMS)

References

    1. 1)
    2. 2)
      • 2. Alvarez, V., Schuhknecht, F.M., Dittrich, J., et al: ‘Main memory adaptive indexing for multi-core systems’. Proc. Tenth Int. Workshop on Data Management on New Hardware, Snowbird, US, June 2014, doi: 10.1145/2619228.2619231.
    3. 3)
      • 9. Curino, C., Jones, E.P.C., Madden, S., et al: ‘Workload-aware database monitoring and consolidation’. Proc. 2011 ACM SIGMOD Int. Conf. on Management of data, Athens, Greece, June 2011, pp. 313–324, doi: 10.1145/1989323.1989357.
    4. 4)
      • 17. Maus, A., Gjessing, S.: ‘A model for the effect of caching on algorithmic efficiency in radix based sorting’. Int. Conf. on Software Engineering Advances, 2007. ICSEA 2007, August 2007, p. 33, doi: 10.1109/ICSEA.2007.6.
    5. 5)
    6. 6)
      • 4. Idreos, S., Kersten, M.L., Manegold, S.: ‘Database cracking’. CIDR, January 2007, pp. 1–8.
    7. 7)
    8. 8)
      • 19. Rahman, N., Raman, R.: ‘Adapting radix sort to the memory hierarchy’, J. Exp. Algorithmics, 2001, 6, (7), pp. 1–30, doi: 10.1145/945394.945401.
    9. 9)
      • 20. Graefe, G., Idreos, S., Kuno, H., et al: ‘Benchmarking adaptive indexing’. Proc. of the Second TPC Technology Conf. on Performance Evaluation, Measurement and Characterization of Complex Systems, Singapore, Singapore, September 2010, pp. 169–184, doi: 10.1007/978-3-642-18206-8_13.
    10. 10)
      • 1. Graefe, G., Kuno, H.: ‘Adaptive indexing for relational keys’. The 2010 IEEE 26th Int. Conf. on Data Engineering Workshops, Long Beach, US, March 2010, pp. 69–74, doi: 10.1109/ICDEW.2010.5452743.
    11. 11)
      • 15. Pavlo, A., Curino, C., Zdonik, S.: ‘Skew-aware automatic database partitioning in shared-nothing, parallel OLTP systems’. Proc. 2012 ACM SIGMOD Int. Conf. on Management of Data, Scottsdale, USA, May 2012, pp. 61–72, doi: 10.1145/2213836.2213844.
    12. 12)
      • 5. Pirk, H., Petraki, E., Idreos, S., et al: ‘Database cracking: fancy scan, not poor man's sort!’. Proc. of the Tenth Int. Workshop on Data Management on New Hardware, Snowbird, US, June 2014, doi: 10.1145/2619228.2619232.
    13. 13)
      • 3. Idreos, S., Manegold, S., Graefe, G.: ‘Adaptive indexing in modern database kernels’. Proc. 15th Int. Conf. on Extending Database Technology, Berlin, Germany, March 2012, pp. 566–569, doi: 10.1145/2247596.2247667.
    14. 14)
      • 12. Maus, A.: ‘ARL, a faster in-place, cache friendly sorting algorithm’. Norsk Informatik Konferranse NIK, November 2002, pp. 85–95.
    15. 15)
      • 13. Polychroniou, O., Ross, K.A.: ‘A comprehensive study of main-memory partitioning and its application to large-scale comparison-and radix-sort’. Proc. of the 2014 ACM SIGMOD Int. Conf. on Management of Data, Snowbird, US, June 2014, pp. 755–766, doi: 10.1145/2588555.2610522.
    16. 16)
      • 10. Ozmen, O., Salem, K., Schindler, J., et al: ‘Workload-aware storage layout for database systems’. Proc. 2010 ACM SIGMOD Int. Conf. on Management of data, Indianapolis, USA, June 2010, pp. 939–950, doi: 10.1145/1807167.1807268.
    17. 17)
    18. 18)
      • 6. Graefe, G., Kuno, H.: ‘Self-selecting, self-tuning, incrementally optimized indexes’. Proc. of the 13th Int. Conf. on Extending Database Technology, Lausanne, Switzerland, March 2010, pp. 371–381, doi: 10.1145/1739041.1739087.
    19. 19)
    20. 20)
http://iet.metastore.ingenta.com/content/journals/10.1049/joe.2016.0068
Loading

Related content

content/journals/10.1049/joe.2016.0068
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading
Print this page
This is a required field
Please enter a valid email address