Kümelemeye dayalı otomatik dizin seçim aracı gerçekleştirimi
Automatic index selection tool implementation based on clustering
Yazar: MEHMET AKİF YANATMA
Danışman: DR. ÖĞR. ÜYESİ MUSTAFA UTKU KALAY
Yıldız Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Mühendisliği Ana Bilim Dalı / Bilgisayar Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control
Dizin: Kümeleme = Clustering ; Kümeleme teknikleri = Cluster technics ; Kümeleme yöntemi = Cluster method ; Veri tabanı = Database ; Veri tabanı sistemleri = Database systems ; Veri tabanı tasarımı = Database design ; Veri tabanı yönetim sistemi = Database management system ; İndeks = Index ; İndeks seçimi = Index selection ; İndeksleme = Indexing

Özet:
Günümüzde sayısal veri miktarının artmasıyla birlikte veri tabanı sistemlerinin kullanımı da artmıştır. Bu kadar çok veri arasından istenilen veriye hızlı bir şekilde ulaşmada ise veri tabanlarının fiziksel tasarımı önemli rol oynamaktadır. Fiziksel veri tabanı tasarımının önemli bir kısmını dizin seçimi oluşturmaktadır. Dizinler, tüm tablonun taranmasına gerek duyulmadan belirli seçim şartlarına uyan satırlara ulaşmayı sağlayan yardımcı yapılardır. Yüzlerce tablo ve binlerce sütun içeren ilişkisel bir veri tabanı için milyarlarca dizin oluşturabilme ihtimali vardır. Ancak bir veri tabanı için dizin sayısı sınırsız bir şekilde arttırılamaz. Çünkü veri tabanında yapılan bir güncellemeden sonra yeni veri tabanı ile tutarlı kalmak için dizinlerin de güncellenmesi gerekir, dolayısıyla dizinlerin bir bakım maliyeti vardır. Diğer taraftan dizinler de birer dosya olduklarından depolama maliyetleri vardır. Bu esaslar göz önünde bulundurulduğunda dizin seçim problemi, NP-tam bir problem olarak karşımıza çıkmaktadır. Böyle bir problem karşısında veri tabanı yöneticisinin bir veri tabanı için dizin seçimi yapması çok zordur.

Bu tez kapsamında dizin seçim problemini otomatik olarak çözmek için dizin seçim aracı geliştirilmiştir. Dizin seçim aracı geliştirilirken kümeleme tekniklerinden yararlanılmıştır. Geliştirilen dizin seçim aracı ile bir iş yükü için uygun dizin kümesi seçerek, veri tabanı yöneticisi üzerindeki iş yükünü hafifletmek ve iş yükünü oluşturan sorguların cevaplanması için gereken toplam zamanın ve toplam disk erişim sayısının azaltılması hedeflenmiştir.

Dizin seçim aracının çalışma prensibi, sorgulardan oluşan bir iş yükünü, birbirine benzer sorgular bir araya gelecek şekilde kümelere ayırmaya çalışmaktır. Benzer sorguları biraraya getirmedeki amaç ise birbirine benzer sorguların ortak nitelikleri üzerinde dizin oluşturma önerisinde bulunmaktır. Böylece oluşturulacak dizinlerin birden çok sorgu için faydalı olması beklenmektedir.

Yapılan performans değerlendirmesi testlerinde iş yükünü oluşturan sorgular ardışık ve eş zamanlı olmak üzere 2 farklı şekilde çalıştırılmıştır. Testler ile iş yükünün işlenmesi için gereken toplam disk erişimi sayısı ve toplam cevap süresi ölçülmüştür. İş yükünün işlenmesi için gereken toplam disk erişimi sayısı ve toplam cevap süresinde,  kümeleme yöntemi ile elde edilen dizin önerilerinin kullanılması ile büyük oranda iyileşme olduğu görülmüştür.

Abstract:
Nowadays, with the increase in the number of digital data, the use of database systems has increased. The physical design of the databases plays an important role in reaching the requested data quickly among such a large number of data. An important part of the physical database design is the index selection. Indexes are auxiliary structures that allow access to rows that match specific selection conditions without having to scan the entire table. There is a possibility of creating billions of indexes for a relational database containing hundreds of tables and thousands of columns. However, the number of indexes for a database cannot be increased limitlessly. Because after an update to the database, the indexes need to be updated to remain consistent with the new database, so the indexes have a maintenance cost. On the other hand, indexes are stored in ordinary files like other data files, so they have storage cost. When these criteria are taken into consideration, the problem of index selection is an NP-complete problem. In the face of such a problem, it is very difficult for the database administrator to select the appropriate indexes for a database.

In this thesis, an index selection tool has been developed to automatically solve the index selection problem. Clustering techniques were used to develop the index selection tool. By selecting the appropriate index set for a workload with the developed index selection tool,  it is aimed to lighten of responsibility of database administrator and to reduce the total time and total disk access count required to answer the queries that make up the workload.

The working principle of the index selection tool is to divide a workload into clusters such that similar queries come together. The purpose of grouping similar queries is to suggest indexing on the common attributes of similar queries. By this way, the indexes to be created are expected to be useful for multiple queries.

In the performance evaluation tests, the queries that constitute the workload were executed in two different ways as consecutive and concurrent. The total number of disk access and total response time required to process the workload were measured with these tests. The total number of disk access count and the total response time required to process the workload has been greatly reduced by the use of index recommendations obtained by the clustering method.