Эффективные методы индексирования данных и выполнения запросов в системах управления базами данных в основной памяти тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Шапоренков, Дмитрий Александрович

• Шапоренков, Дмитрий Александрович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Шапоренков, Дмитрий Александрович

1. Введение

2. Предпосылки СУБД-ОП

2.1. Особенности архитектур современных компьютеров.

2.1.1. Процессоры.

2.1.1.1. Внутренний параллелизм.

2.1.1.2. Предсказание переходов.

2.1.2. Система памяти

2.1.2.1. Кэш-память.

2.1.2.2. Характеристики кэш-памяти.

2.1.2.3. Виды кэш-промахов.

2.1.2.4. Явное управление кэш-памятью.

2.1.2.5. Устройство трансляции адресов

2.1.2.6. Стоимость доступа к памяти.

2.1.2.7. Методы измерения эффективности доступа к памяти.

2.1.2.8. Пример.

2.1.3. Особенности многопроцессорных систем.

2.2. Архитектура традиционных СУБД и СУБД-ОП.

2.2.1. Компоненты архитектуры традиционной СУБД

Введение диссертации (часть автореферата) на тему «Эффективные методы индексирования данных и выполнения запросов в системах управления базами данных в основной памяти»

В течение нескольких последних десятилетий системы управления базами данных (СУБД) стали одним из основных приложений вычислительной техники. Сегодня успешная деятельность многих организаций, таких как государственные учреждения, предприятия, банки, магазины напрямую зависит от СУБД. Объемы данных, хранимые в таких системах, огромны и часто достигают многих терабайт [3]. Более того, требования прикладных областей к размерам хранимых данных постоянно растут [3, 1].

Организация таких объемов данных является нетривиальной задачей, различными аспектами которой исследователи в области СУБД занимаются начиная примерно с 70х гг. 20 века [4, 1]. База данных размером в несколько терабайт малополезна, если нет эффективного способа доступа к хранимым данным. Запросы пользователей к базе данных могут иметь различный характер - в одних случаях для получения ответа требуется просмотреть все содержимое базы данных, но не менее часто запросы затрагивают лишь небольшую часть хранимых данных. Типичным примером второго рода является проведение операции снятия денег со счета через банкомат. Для такой операции обычно интерес представляет лишь счет данного пользователя, идентифицируемый номером его кредитной карточки. Просмотр счетов всех пользователей банка в таком случае был бы очевидно неэффективным решением.

Традиционно СУБД хранят данные во вторичной памяти, такой как жесткие диски [3, 1]. Основной причиной этого является большой объем данных, который не может быть размещен в основной (оперативной) памяти компьютера. С другой стороны, архитектуры современных вычислительных систем ориентированы исключительно на обработку данных в основной памяти. В частности, процессор предоставляет обычно лишь инструкции для работы с данными, находящимися в памяти и во встроенных регистрах [43, 26]. В результате традиционные СУБД вынуждены значительное время тратить на пересылку данных из вторичной памяти в основную и обратно [1].

В контексте вышесказанного естественной является идея разместить базу данных не во вторичной, а в основной памяти, приводящая к появлению СУБД в основной памяти (СУБД-ОП) [1, 34]. Первые исследования, относящиеся к таким системам, появились примерно в начале 80х гг. 20 века [34, 3]. Наиболее привлекательная черта СУБД-ОП — отсутствие необходимости обращаться к медленной вторичной памяти для выполнения пользовательских запросов, что дает выигрыш на величину порядка по сравнению с традиционными СУБД [1, 19, 62]. Разумеется, ограниченный объем основной памяти влияет на максимальный размер базы данных, которую можно разместить в основной памяти. Однако не всегда объем БД исчисляется терабайтами, для многих приложений достаточно и нескольких гигабайт. Кроме того, на протяжении последних десятилетий наблюдается устойчивая тенденция быстрого роста объема ОП в компьютерах [26, 58], частично связанная с удешевлением микросхем памяти [58, 11, 21].

Например, рассмотрим гипотетическую реляционную БД, содержащую информацию о жителях крупного города с населением 4 млн человек. Одно из отношений, Citizens, может иметь вид:

CREATE TABLE Citizens (ID int NOT NULL,

FirstName char (10) NOT NULL, LastName char (25) NOT NULL, Address char (30) NOT NULL, Phone char (7))

Размер записи этого отношения составит примерно 80 байт, и для хранения информации о всех жителях города потребуется, таким образом, около 400 мегабайт. С учетом того, что в 2005 году объем ОП в 2 гигабайта не является редкостью для серверной системы, вся БД (состоящая из нескольких отношений) может быть целиком размещена в памяти сервера СУБД.

Проблемы оптимизация выполнения запросов в традиционных реляционных СУБД хорошо формализованы и исследованы [1]. На протяжении последних десятилетий были разработаны критерии эффективности методов выполнения запросов, и современные реляционные СУБД, как правило, способны выбирать наиболее эффективные пути выполнения запросов без помощи пользователя или администратора [1, б]. Однако с переносом данных в ОП традиционные критерии эффективности перестают иметь смысл [11, 21]: в традиционных СУБД оптимизация запросов обычно направлена на минимизацию числа обращений к медленной вторичной памяти, а в СУБД-ОП такие обращения не происходят вообще. Таким образом, необходимы новые критерии эффективности и, возможно, иные методы выполнения запросов.

Эффективное выполнение запросов в СУБД-ОП и является основным предметом данной работы. Наши исследования касаются эффективных индексных структур и методов выполнения запросов, которые позволяют полностью использовать возможности современных компьютеров. Мы систематизируем методы оптимизации работы с данными в ОП, а также предлагаем ряд новых индексных структур и алгоритмов выполнения операций и оцениваем их эффективность [51, 52, 54, 53].

Данная работа имеет следующую структуру. В главе 2 рассматриваются особенности современных компьютерных архитектур и обосновывается, почему традиционные СУБД, рассчитанные на хранение данных на диске, не позволяют получить максимальную производительность при использовании их в качестве СУБД-ОП. Там же показано, какие компоненты СУБД требуют пересмотра для СУБД-ОП. Глава 3 описывает общие идеи, которые применяются для повышения эффективности алгоритмов и структур данных в предположении, что данные располагаются в основной памяти. Эти идеи проиллюстрированы небольшими примерами, поясняющими их применение для простых задач, которые являются частями более сложных проблем, возникающих при реализации СУБД. В главе 4 мы применяем эти общие идеи к задачам оптимизации операции естественного соединения и соединения по предикату над множественнозначными атрибутами. Мы предлагаем мульти-индексы — структуру, которая в компактном виде хранит результат естественного соединения и допускает быстрое обновление при изменении индексируемых отношений. Мы также исследуем производительность нескольких алгоритмов для выполнения операции соединения по предикату над множественнозначными атрибутами в СУБД-ОП и выясняем, что наиболее эффективными являются методы, основанные на использовании инвертированных списков. Мы предлагаем модификацию этих методов, учитывающую специфические для СУБД-ОП критерии эффективности, и экспериментально демонстрируем, что эта модификация сокращает время выполнения соединения.

Глава 2.

Предпосылки СУБД-ОП

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Шапоренков, Дмитрий Александрович

4.3.5. Выводы

В данном разделе мы исследовали производительность различных алгоритмов для выполнения операции соединения по предикату над множе-ственнозначными атрибутами в предположении, что данные находятся в основной памяти. Наши исследования показывают, что алгоритмы, основанные на использовании инвертированных файлов - IFNL, IFJ и IX, оказываются значительно эффективнее, чем алгоритмы, применяющие для ускорения соединения сигнатуры и метод распределения. Мы также предложили специализированную индексную структуру - индекс пересечения, которая позволяет свести вычисление результата соединения к простому обходу этой структуры.

Мы рассмотрели модифицированные варианты алгоритмов IFNL и IFJ, которые используют технику логического распределения для сокращения активного набора данных и увеличения шансов их переиспользования в кэш-памяти. Этот прием оказался эффективным для алгоритмаIFJ, но не для алгоритма IFNL, поскольку для IFNL дополнительные накладные расходы, связанные с необходимостью выбора значения для обработки на очередном этапе, перевешивают преимущества уменьшающегося количества кэш-промахов. Это означает, что алгоритм IFNL больше подходит для отношений небольших размеров, в то время как алгоритм IFJ более пригоден для больших отношений, поскольку он лучше масштабируется с ростом \S\. Мы также изучили эффект сжатия инвертированных файлов и промежуточных результатов и сделали вывод, что основным положительным эффектом сжатия является сокращение требуемого объема памяти, но это достигается только в случае, когда длины инвертированных списков и размер результата достаточно велики. Как средство уменьшения размера списков и сокращения количества кэш-промахов первого обращения сжатие себя не оправдывает, поскольку вызывает значительные накладные расходы на распаковку сжатых данных.

Глава 5.

Заключение

В данной работе исследованы аспекты СУБД-ОП, относящиеся к индексированию данных и эффективному выполнению запросов. В работе получены следующие основные результаты:

1. Предложены критерии оценки эффективности структур данных и алгоритмов для СУБД-ОП, учитывающие неоднородность доступа к основной памяти в современных вычислительных системах.

2. Построена классификация, обобщающая большинство известных методов оптимизации структур данных и алгоритмов для эффективного использования кэш-памяти процессора.

3. Реализована среда для проведения экспериментов с индексными структурами и алгоритмами выполнения реляционных операций в основной памяти Memphis, которая использована при проведении многих экспериментальных проверок.

4. Предложен и экспериментально проверен метод оптимизации операции соединения на основе мульти-индексов в СУБД-ОП, показана его сравнительная эффективность по сравнению с методом хэш-соединения в зависимости от параметров входных отношений.

5. Исследованы различные алгоритмы для выполнения операции соединения по предикату над множественнозначными атрибутами в

СУБД-ОП, предложена модификация алгоритма IFJ (Inverted File Join), основанного на использовании инвертированных файлов, для лучшего использования кэш-памяти и экспериментально продемонстрировано, что эта модификация приводит к уменьшению времени выполнения соединения.

Данная работа демонстрирует необходимость применения специальных методов для реализации полноценных СУБД-ОП, которые эффективно используют кэш-память процессора, устройство предсказания переходов и другие особенности архитектуры современных компьютеров. Предложенные в работе алгоритмы могут применяться в СУБД-ОП для поддержки расширенного набора реляционных операций, включающего операции над множественнозначными атрибутами, во многих случаях предоставляющими естественный способ выражения понятий предметной области. Рассмотренные методы имеют также важное значение при исследовании следующего шага в развитии СУБД с точки зрения использования архитектурных особенностей компьютерных систем — СУБД, которые могут эффективно работать с данными на нескольких уровнях иерархии памяти, обеспечивая оптимальное быстродействие как для данных, находящихся на диске, так и для данных в основной памяти.

Список литературы диссертационного исследования кандидат физико-математических наук Шапоренков, Дмитрий Александрович, 2006 год

1. Гарсиа-Молина Г., Ульман Д., Уидом Д. Системы баз данных. Полный курс. / Пер. с англ. — М.:Вильямс, 2003.

2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. / Пер. с англ. — М.:Мир, 1998.

3. К.Дою.Дейт. Введение в системы баз данных. 8-е издание. / Пер. с англ. — М.:Вильямс, 2005.

4. М.Р.Когаловский. Энциклопедия технологий баз данных.— М.:Финансы и статистика, 2002.

5. Руссинович М., Соломон Д. Внутреннее устройство Microsoft Windows 2000. / Пер. с англ. — СПб.:Русская редакция : Питер, 2001.

6. Access Path Selection in a Relational Database Management System. / P. G. Selinger, M. M. Astrahan, D. D. Chamberlin et al. // Proc. of the SIGMOD 1979 Conference. ACM, 1979.- P. 23-34.

7. ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging. / C. Mohan, D. J. Haderle, B. G. Lindsay et al. // ACM Trans. Database Syst.— 1992. Vol. 17, no. 1. - P. 94-162.

8. Bayer R., McCreight E. M. Organization and Maintenance of Large Ordered Indexes. // Record of the SIGFIDET 1970 Workshop. ACM, 1970. - P. 107-141.

9. Bohannon P., Mcllroy P., Rastogi R. Main-Memory Index Structures with Fixed-Size Partial Keys. // Proc. of the SIGMOD 2001 Conference.-2001.

10. Boncz P. A., Manegold S., Kersten M. L. Database Architecture Optimized for the New Bottleneck: Memory Access. // Proc. of the VLDB 1999 Conference. — Morgan Kaufmann, 1999. — P. 54-65.

11. Boncz P., Kersten M. Monet: an Impressionist Sketch of an Advanced Database System. — 1995.

12. Cache-Conscious Concurrency Control of Main-Memory Indexes on Shared-Memory Multiprocessor Systems. / S. K. Cha, S. Hwang, K. Kim, K. Kwon // Proc. of the VLDB 2001 Conference. — Morgan Kaufmann, 2001.-P. 181-190.

13. Cai J.-Y. et al. On the Complexity of Join Predicates // Proc. of the PODS 2001 Conference. 2001. - P. 207-214.

14. Chatterjee S., Sen S. Cache-Efficient Matrix Transposition. // Proc. of the HPCA 2000 Conference. 2000. - P. 195-205.

15. Chilimbi Т. M., Hill M. D., Larus J. R. Cache-Conscious Structure Layout, // Proc. of the PLDI 1999 Conference. 1999. - P. 1-12.

16. Chilimbi Т. M., Larus J. R. Using Generational Garbage Collection To Implement Cache-Conscious Data Placement. // Proc. of the ISMM 1998 Conference. 1998. - P. 37-48.

17. Copeland G. P., Khoshafian S. A Decomposition Storage Model. // Proc. of the SIGMOD 1985 Conference. ACM Press, 1985. - P. 268-279.

18. Dali: A High Performance Main Memory Storage Manager. / H. V. Jagadish, D. F. Lieuwen, R. Rastogi et al. // Proc. of the VLDB 1994 Conference. — Morgan Kaufmann, 1994. — P. 48-59.

19. Data Compression in Full-Text Retrieval Systems. / Т. C. Bell, A. Moffat,

20. C. G. Nevill-Manning et al. // JASIS. 1993. - Vol. 44, no. 9. - P. 508531.

21. DBMSs on a Modern Processor: Where Does Time Go? / A. Ailamaki,

22. D. J. DeWitt, M. D. Hill, D. A. Wood // Proc. of the VLDB 1999 Conference. Morgan Kaufmann, 1999. - P. 266-277.

23. Denning P. Locality (unpublished manuscript). — 2005.

24. Graefe G. Query Evaluation Techniques for Large Databases. // ACM Comput. Surv.- 1993. Vol. 25, no. 2. - P. 73-170.

25. Hankins R. A., Patel J. M. Data Morphing: An Adaptive, Cache-Conscious Storage Technique. // Proc. of the VLDB 2003 Conference. — 2003.-P. 417-428.

26. Helmer S., Moerkotte G. Evaluation of Main Memory Join Algorithms for Joins with Set Comparison Join Predicates. // Proc. of the VLDB 1997 Conference. — Morgan Kaufmann, 1997. — P. 386-395.

27. Hennessy J. L., Patterson D. A. Computer Architecture: A Quantitative Approach. — 3rd edition. — Morgan Kaufmann, 2002.

28. Improving Hash Join Performance through Prefetching. / S. Chen, A. Ailamaki, P. B. Gibbons, Т. C. Mowry // Proc. of the HDMS 2004 Conference. — 2004.

29. Intel Corporation. IA-32 Intel Architecture Optimization Reference Manual. 2005.

30. Intel Corporation. IA-32 Intel Architecture Software Developer's Manuals. 2005.

31. Intel Corporation. Intel С++ Compiler Documentation. — 2005.

32. Intel VTune Performance Analyzer // http://www.mtel. com/software/products/vtune/.

33. Kim K., Cha S. K., Kwon K. Optimizing Multidimensional Index Trees for Main Memory Access. // Proc. of the SIGMOD 2001 Conference.— 2001.

34. Lehman T. JCarey M. J. A Study of Index Structures for Main Memory Database Management Systems. // Proc. of the VLDB 1986 Conference. — Morgan Kaufmann, 1986. P. 294-303.

35. Litwin W. Linear Hashing: A New Tool for File and Table Addressing. // Proc. of the VLDB 1980 Conference. IEEE Computer Society, 1980. -P. 212-223.

36. Li Z., Ross K. A. Fast Joins Using Join Indices. // VLDB Journal — 1999.-Vol. 8, no. l.-P. 1-24.

37. Mamoulis N. Efficient Processing of Joins on Set-Valued Attributes // Proc. of the SIGMOD 2003 Conference. 2003. - P. 157-168.

38. Manegold S., Boncz P. A., Kersten M. L. What Happens During a Join? Dissecting CPU and Memory Optimization Effects. // Proc. of the VLDB 2000 Conference. Morgan Kaufmann, 2000. - P. 339-350.

39. Manegold S., Boncz P. A., Kersten M. L. Generic Database Cost Models for Hierarchical Memory Systems. // VLDB. 2002. - P. 191-202.

40. Manegold S., Boncz P. A., Kersten M. L. Optimizing Main-Memory Join on Modern Hardware. // IEEE Trans. Knowl. Data Eng. — 2002. — Vol. 14, no. 4.-P. 709-730.

41. Manegold S., Boncz P. A., Nes N. Cache-Conscious Radix-Decluster Projections. // Proc. of the VLDB 2004 Conference. — Morgan Kaufmann, 2004. P. 684-695.

42. Manegold S., Boncz P. Cache-Memory and TLB Calibration Tool // http://monetdb. cwi. nl/ Calibrator/doc/calibrator.pdf.

43. Nonlinear Array Layouts for Hierarchical Memory Systems. / S. Chatterjee, V. V. Jain, A. R. Lebeck et al. // Proc. of the ICS 1999 Conference. 1999.- P. 444-453.

44. Oracle Corporation. SQL 2003 Standard Support in Oracle Database lOg. An Oracle White Paper. 2003.

45. PennerM., Prasanna V. K. Cache-Friendly Implementations of Transitive Closure. // Proc. of the PACT 2001 Conference.- IEEE Computer Society, 2001. P. 185-.

46. Rao J., Ross K. A. Cache Conscious Indexing for Decision-Support in Main Memory. // Proc. of the VLDB 1999 Conference. — Morgan Kaufmann, 1999. P. 78-89.

47. Rao J., Ross K. A. Making B+-Trees Cache Conscious in Main Memory. // Proc. of the SIGMOD 2000 Conference. ACM, 2000. - P. 475-486.

48. Ross K. A. Selection Conditions in Main Memory. // ACM Trans. Database Syst.- 2004.- Vol. 29.- P. 132-161.

49. Set Containment Joins: The Good, The Bad and The Ugly. / K. Ramasamy, J. M. Patel, J. F. Naughton, R. Kaushik // Proc. of the VLDB 2000 Conference. Morgan Kaufmann, 2000. - P. 351-362.

50. Shaporenkov D. Multi-Indices A Tool for Optimizing Join Processing in Main Memory // Proc. of the Baltic DBIS 2004 Conference.- 2004.-P. 105-114.

51. Shaporenkov D. Performance Comparison of Main-Memory Algorithms for Set Containment Joins // Proc. of the SYRCoDIS 2004 Symposium.— 2004.-P. 17-21.

52. Shaporenkov D. Efficient Main-Memory Algorithms for Set Containment Join Using Inverted Lists // Proc. of the ADBIS 2005 Conference. — 2005.-P. 139-152.

53. Shaporenkov D. Partitioning Inverted Lists for Efficient Evaluation of Set-Containment Joins in Main Memory // Proc. of the SYRCoDIS 2005 Symposium. 2005. - P. 40-46.

54. Shatdal A., Kant C., Naughton J. F. Cache Conscious Algorithms for Relational Query Processing. // Proc. of the VLDB 2004 Conference. — Morgan Kaufmann, 1994. P. 510-521.

55. Smith A. J. Cache Memories. // ACM Comput. Surv.- 1982.- Vol. 14, no. 3. P. 473-530.

56. Sokolinsky L. B. Lfu-k: An effective buffer management replacement algorithm. // Proc. of the DAS FA A 2004 Conference. 2004,- P. 670681.

57. Stallings W. Computer Organization and Architecture: Designing for Performance. — 6th edition. — Prentice Hall, 2003.

58. Stallings W. Operating Systems: Internals and Design Principles. — 5th edition. — Prentice Hall, 2003.

59. Sun Microsystems Inc. UltraSPARC IV Processor Specifications. — 2005.

60. Sutter H. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software // Dr.Dobb's Journal — 2005. — Vol. 30, no. 3.

61. The Architecture of the Dali Main-Memory Storage Manager. / P. Bohannon, D. F. Lieuwen, R. Rastogi et al. // Multimedia Tools Appl — 1997. Vol. 4, no. 2. - P. 115-151.

62. Valduriez P. Join Indices. Ц ACM Trans. Database Syst1987.-Vol. 12, no. 2.-P. 218-246.

63. Weaving Relations for Cache Performance. / A. Ailamaki, D. J. DeWitt, M. D. Hill, M. Skounakis // Proc. of the VLDB 2001 Conference. Morgan Kaufmann, 2001.- P. 169-180.

64. Whaley R. C., Dongarra J. Automatically Tuned Linear Algebra Software. // Proc. of the PPSC 1999 Conference. 1999.

65. Witten I., Moffat A., Bell T. Managing Gigabytes : Compressing and Indexing Documents and Images.— 2nd edition.— Morgan Kaufmann, 1999.

66. Zhou J., Ross K. A. Implementing Database Operations Using SIMD Instructions. // Proc. of the SIGMOD 2002 Conference. ACM, 2002.-P. 145-156.