Trigram ile SQL Server Üzerinde Hızlı Arama

Elimizde bir müşteri listesi var ve bu veri 20 milyon satır içeriyor. Kafa karışıklığı yaratabilir diye en baştan yazayım. Buradaki verilerin hiçbiri gerçek veri değil. Rastgele isim ve soy isimlerden türetilmiş fake verileri kullanıyoruz. 

Customers tablosımda görülebileceği üzere bir TCNUMBER alanı bulunuyor.

Amacımız TC kimlik numarası içinde geçen herhangi bir stringi getirmek olsun. Burada akıllara gelen ilk arama şekli wildcard kullanmak. Yani like ile arama gerçekleştirmek.

İçerisinde "4248373" geçen kimlik numaralarını bulmak için sorgumuzu aşağıdaki gibi çalıştırabiliriz.

Çıktı yaklaşık 4 saniyede geldi ve 597 547 adet page okudu.  Her bir page 8 KB’tan oluşuyor.

Bu da 597 547 * 8KB / 1024 = 4,6 GB'a tekabül ediyor. Yani 8 satırlık bir sonuç döndüren bir sorgu 4.6 GB’lık bir veriyi okuyor. Bu okuduğu verileri byte byte karşılaştırmak için harcadığı CPU kaynağını söylemiyorum bile. Burada aynı anda sorgu çeken sadece bir kişiden bahsediyoruz.

Peki aynı anda 10 kişi bu işlemi gerçekleştirirse ne olur ona bakalım. Bunun için ben basit bir uygulama yazdım ve rastgele numaraları like ile TCNUMBER sütununda arıyoruz. Elde ettiğimiz sonuç ise aşağıdaki gibi. Ortalama 25 saniye sürüyor.

Bu işlemler gerçekleşirken SQL Server'ın CPU kullanımı da tavan yapmış durumda.

Non-Clustered Index Kullanmak

Yavaşlık sorununu çözmek için akla gelen ilk konu index meselesi. Zira biliyoruz ki index, sorgu performansı için en önemli konu.

TCNUMBER alanına göre sisteme bir index koyalım.

CREATE INDEX IX1_TCNUMBER ON CUSTOMERS (TCNUMBER)

Şimdi sorgumuzu tekrar çekelim.

SQL Server özellikle koyduğumuz indexi kullansın diye buraya with ekliyorum. Normalde SQL zaten bu indexi kullanır ama biz işimizi garantiye alalım.

Görüldüğü gibi değişen pek bir şey olmadı. Bunun sebebi aslında oldukça açık. Başında ve sonunda % karakteri olan aramalarda index bir işe yaramaz. Çünkü belli bir sırada değildir. Neticede içinde herhangi bir yerde geçen bir string arıyoruz.

Oysa başında % olmadan bir arama yapmayı deneseydik. Elde edeceğimiz sonuç oldukça başarılı olacaktı. Aşağıdaki görselde görüleceği gibi belli bir formatta ile başlar şeklinde yaptığımız bir arama işlemi indexi kullandı ve toplamda 18 page okuyarak 0 milisaniyede sorguyu getirdi. Peki bu ne anlama geliyor?

Bu sorgunun 52 374 / 18 = 2 900 kat yani yaklaşık 3 000 kat daha hızlı çalışması demek. Ama ne yazık ki biz %% ile içinde geçen bir kelimeyi bulmak istiyoruz. Kısaca bu görevde non-clustered index işe yaramadı diyebiliriz.

ColumnStore Index Eklemek

SQL Server’da bir başka index yöntemi de column store index. Bu sütunun kendisini indexleyen bir yapı ve bu tarz uygulamalar için çözüm olabilir. O halde hemen bir column store index ekleyelim.

CREATE NONCLUSTERED COLUMNSTORE INDEX IX2_CS_TCNUMBER ON [dbo].[CUSTOMERS]
(
      [TCNUMBER]
)

Şimdi sorgumuzu tekrar çalıştıralım. Bu kez işlem yaklaşık 3 saniyeye inmiş durumda. Okuma sayısı da 52 000’den 44 300’e inmiş görünüyor. Yani sorunumuz yine tam anlamıyla çözülmedi.

Full-Text Search Kullanmak

Derdimiz metin arama olduğu için ilk akla gelenlerden biri de full-text search işlemi olabilir. Gelin onu da deneyelim. Bunun için önce tablo üzerinde full-text tanımlamamız gerekiyor.

Burada özellikle TCNUMBER ile birlikte ADDRESSTEXT alanını da fulltexte dahil ediyorum. Bunun sebebini açıklayacağım.

Full-texti tanımladık. Artık sorgu çekebiliriz. Full-text konusunu iyi anlamak için önce ADDRESSTEXT alanından bir arama gerçekleştirmek istiyorum.

Örneğin adres alanı içinde “DEĞİRMENDERE” geçen kayıtları arayalım.

Sorgumuz geldi. Şimdi de kaynak kullanımına bakalım. Görüldüğü gibi oldukça fazla miktarda kaynak kullanımı söz konusu. 594 150 page okumuş ki her biri 8KB. Ayrıca yaklaşık 17 saniye sürmüş. Bu sorgudan yaklaşık 12 000 satır kayıt döndü. Adres gibi bir alanın içinde like ile bir kelime aramak TCNUMBER alanında aramaya benzemiyor. Sistemi oldukça yoruyor.

Şimdi de aynı işlemi full-text search ile yapalım.

Sorgumuz geldi. Bu kez değerlerimiz oldukça iyi. Okuma sayısı 42 064 olmuş. Süre ise 451 milisaniye. Oldukça iyi. Sonuçta 20 milyon satırlı bir tablo içinde bir metin alanının herhangi bir yerinde geçebilecek bir “DEĞİRMENDERE” kelimesini aradık ve hızlı sonuç aldık. Toplamda 12 037 satır geldi.

Full-text search kelimeleri indexliyor. Yani kelimenin tamamını yazdığımızda ya da “DEĞİRME*” gibi bir kısmını yazıp ile başlar şeklinde gönderdiğimizde çok hızlı çalışıyor. Şimdi “DEĞİRMEN*” şeklinde kullanalım.

Bu kez 68 000 satır geldi. Gördüğünüz gibi içinde “DEĞİRM” geçen tüm adresleri getirdi.

Şimdi değerlere bir bakalım. 20 milyon satır. İçinde adres verisinin bulunduğu bir kolonda “DEĞİRMEN” ile başlayan kelimeleri arıyoruz. Süre 777 milisaniye ve 272 544 page okunmuş. Burada dönen sonuç 68 000 satır olduğu için bu kadar page okuma işlemi normal.

Sonuç olarak full-text search işe yarıyor diyebiliriz. Ama bizim derdimiz neydi? İle başlar değil içerir şeklinde arama yapmak.

O halde “*EĞİRMEN*” kelimesini arayalım.

Görüldüğü gibi kayıt gelmedi. Çünkü EĞİRMEN diye bir kelime yok. Başına joker karakter koysam da gelmedi.

Aynısını TCNUMBER alanı için uygulayalım. Öyle ya biz bu alana da full-text index eklemiştik. Kimlik numarası 9146823 ile başlayanları getirmek istediğimizde sorgu doğru ve hızlı çalışıyor.

Hem de oldukça hızlı.

Aranan kelimenin başına ve sonuna * işareti koyduğumda ise yine sadece kelimenin başlangıcı aranan kelime olanları getiriyor. Yani 146823 ile başlayanları getiriyor. İçinde “146823” geçenleri getirmiyor.

Özetle full-text arama da işimizi tam anlamıyla görmedi.

Trigram Kullanımı

SQL Server ve diğer veri tabanı yönetim sistemleri veriyi dikeyde aramak için tasarlanmıştır. Yani satırlar üzerinde doğru optimize edilirse satır sayısı ne kadar olursa olsun performanslı bir şekilde arama işlemi gerçekleşir. Ancak %% kalıbı ile aradığımızda sistem yatayda bir arama gerçekleştirir.

Örneğin 14682321186 ifadesinin içinde 82321 ifadesini ararken sürekli bir kaydırma durumu ile karşılaştırma işlemi yapılır.

Gördüğünüz gibi  her seferinde bir kaydırma işlemi ile arama gerçekleşiyor. Üstelik bu işlem yalnızca bir satırda yapılan işlem. Bunun gibi 20 milyon satır var. Bu durumda tablodaki satır sayısı, aranan stringin uzunluğu, arama yapılan kolonun uzunluğu, veri tipi gibi etkenler ile oldukça verimsiz bir arama şekli karşımıza çıkıyor. İşte bu durum like %% ile aramanın ne kadar verimsiz olduğunu açıklıyor.

Veri tabanları dikeyde çalışmak için tasarlanmıştır demiştik. Doğru index ve BiTree algoritması ile çok hızlı şekilde arama yapabiliriz. Ama verimiz yan yana tren vagonu dizilen harfler.  Yani yatay veri. O zaman bu yatay veriyi dikey hale getirebilirsek işimiz çözülecek demektir.

Trigram dediğimiz yapı ile bu işlemi gerçekleştirebiliriz. Trigram, bir kelimeyi üçerli şekilde parçalayarak satırlara ekleme işlemine verilem isim.

Örneğin 14682321186 stringini ele alalım. Trigramı aşağıdaki gibi dokuz satırdan oluşur.

Bu trigram içerisinde arama yapabilmek için arama yapacağımız kelimeyi de trigram olarak parçalamamız gerekiyor.

Arama yapacağımız veri 82321. Şimdi bunun trigramlarına bakalım. Yani üçerer karakter olacak şekilde parçalayalım.

Sırada artık satır satır 823 232 ve 321 verilerini dokuz satırdan oluşan tablo içinde aratmak kalıyor. Bu tabloya da bir index eklersek bu bildiğimiz dikey arama. Hani bizim iyi olduğumuz taraf.

Aslında bu teknolojinin adı Ngram. Yani burada N sayısını biz belirliyoruz. Örneğin Bigram ikili olarak parçalama, Trigram ise üçlü olarak parçalama. En çok tercih edilen Trigram.

Bu kadar teorik bilgiden sonra gelin şimdi bu işi SQL tarafında nasıl yapıyoruz ona bir göz atalım.

SQL Server üzerinde Trigram

Öncelikle şunu söylemeliyim ki SQL Server ve TSQL’de hazır bir trigram yapısı yok. PosgreSQL’de bu yapı bir eklenti ile geliyor. Biz burada kendi trigram yapımızı kendimiz oluşturacağız.

Her şeyden önce bizim herhangi bir string ifadeyi trigram tablosuna çevirecek bir table valued functiona ihtiyacımız var. Aşağıda bu fonksiyonun kodlarını paylaşıyorum. Bu fonksiyonda ben hızlı olsun diye maximum 16 adet trigram ile sınırladım. Çünkü TC kimlik numarası zaten 9 tane trigram çıkarıyor. Bu sayı duruma göre bu değer değiştirilebilir.

CREATE function dbo.strToTrigram(@String varchar(100))
Returns Table
As
Return
(
Select substring(@string,v,3) Trigram,T.v  Seq
            from
            (
                values
                    (1),(2),( 3),(4),(5),(6),(7),(8),
                    (9),(10),(11),(12),(13),(14),(15),(16)
            ) as T (v)
                  where LEN(substring(@string,v,3))='3'
)

 Şimdi de bu fonksiyonun kullanımını görelim.

Burada Trigram alanı parçalanmış değeri getirirken Seq alanı ise bu trigramın string ifade içerisindeki sıra numarasını getirmekte. Bu bize sorgularımızda çok yardımcı olacak.

Şimdi artık sıra geldi customers tablosundaki her bir satırın trigramını çıkarmaya. Bu ne demek? 20 milyon satır * 9=180 milyon satırlık bir trigram. Burada kimlik numarası uzunluğu sabit olduğu için bu değeri tahmin etmek kolay.

Şimdi bir tablo oluşturalım. Tablomuzun adı CUSTOMER_TCNR_TRIGRAM olsun.

ID: Otomatik artan bir integer alan. Tablomuzun primary keyi.
ROWID: Customers tablosundaki ID alanının referans numarası.
TRIGRAM: Parçalanan trigram değeri.
SEQ: Trigramın sıra numarası.

Şimdi sıra geldi bu 20 milyon satırlık tablonun trigramını çıkarıp CUSTOMER_TCNR_TRIGRAM tablosuna insert etmeye.

Burada 20 milyon satırı tek seferde aktarmak yerine birer milyon aktarmak daha kolay olacaktır. Aşağıdaki kod bloğu bu işlemi 20 kere çalıştıran bir döngü ve her seferinde 1 milyon satırlık müşteri kaydını trigramlarına ayrılarak CUSTOMER_TCNR_TRIGRAM tablosuna insert edilmesi işlemini gerçekleştiriyor.

DECLARE @MAXID AS INT
DECLARE @I AS INT=0
WHILE @I<20>
BEGIN
SELECT @MAXID=MAX(ROWID)   FROM CUSTOMER_TCNR_TRIGRAM
SET @MAXID=ISNULL(@MAXID,1)
      INSERT INTO CUSTOMER_TCNR_TRIGRAM  (ROWID,TRIGRAM,SEQ)
            SELECT   C.ID,T.Trigram,T.seq FROM CUSTOMERS C
                  CROSS APPLY (SELECT * FROM dbo.strToTrigram(C.TCNUMBER)) t
            WHERE C.ID BETWEEN @MAXID AND @MAXID+1000000 AND t.seq<>''
            ORDER BY C.ID,t.seq
      SET @I=@I+1
END

Bu sorgunun sonunda bir satır için satırın değerine ve trigram değerlerine bakacak olursak satırdaki TCNUMBER kolonu için dokuz satır trigram oluştuğunu görebiliriz.

Toplamda 20 milyon satırlık bir tablo için 180 milyon satırlık bir trigram oluşmuş durumda.

Trigram ile arama

Artık arama sorgumuzu yazabiliriz. Normalde PosgreSQL veri tabanında trigram ile alakalı hazır komutlar ve bir eklenti var. Ancak gördüğüm kadarıyla SQL Server’da böyle bir eklenti ya da bir komut yok. Bu nedenle şimdilik benim yazdığım algoritmayı kullanacağız. Buradaki algoritmayı tamamen özgün ve bana ait bir çalışma.

Tabi hızlı arama için trigram tablosunda bir takım indexlere ihtiyacımız var. O indexlerin scriptlerini de burada paylaşıyorum.

ALTER TABLE [dbo].[CUSTOMER_TCNR_TRIGRAM ] ADD  CONSTRAINT [PK_TCNOTRIAGRAM]
PRIMARY KEY CLUSTERED
(
      [ID] ASC
)
CREATE NONCLUSTERED INDEX [IX1] ON [dbo].[CUSTOMER_TCNR_TRIGRAM ]
(
      [TRIGRAM] ASC
)
INCLUDE([ROWID],[SEQ])
CREATE NONCLUSTERED INDEX [IX2] ON [dbo].[CUSTOMER_TCNR_TRIGRAM ]
(
      [ROWID] ASC
)

Arama işlemini gerçekleştiren procedureümüz dinamik bir SQL cümlesi oluşturuyor ve biz oluşan bu SQL cümlesini çalıştırıyoruz.

Önce aşağıda ek olarak da yer vereceğimiz procedureümüzü bir çalıştıralım ve sonuca bakalım.

Aradığımız patern '4248373' yani kimlik numarası içinde bu kalıbın geçtiği kayıtları bulmaya çalışacağız.

Arama sonucunca 93 satır kayıt geldi. Makalenin başında bu sorguyu like ile çağırdığımızda yaklaşık 3 saniye sürmüştü ve 41 bin page okumuştu. Bu sorgu ise 64 milisaniye sürdü ve toplamda yaklaşık 5 bin page okundu. 

Stored procedureümüz ise şu şekilde:

create PROC [dbo].[SEARCH_TCNUMBER]  
@STRINGID AS VARCHAR(100)
AS
DECLARE @DATE AS DATETIME
set @DATE =GETDATE()

SET @STRINGID=REPLACE(@STRINGID,'%','')
DECLARE @SQL AS NVARCHAR(MAX)=''
DECLARE @LASTSQL AS NVARCHAR(MAX)=''
DECLARE @STR AS VARCHAR(100)
DECLARE @I AS INT=1
DECLARE @COUNTER AS INT=1
DECLARE CRS CURSOR FOR SELECT TRIM(trigram) FROM dbo.strToTrigram(@STRINGID) ORDER BY SEQ
OPEN CRS
FETCH NEXT FROM CRS INTO @STR
WHILE @@FETCH_STATUS=0
BEGIN
      IF @I=1
      BEGIN
            SET @SQL='SELECT ROWID INTO #T FROM CUSTOMER_TCNR_TRIGRAM T1 '
            SET @SQL=@SQL+CHAR(13)+'WHERE TrIgram LIKE '''+@STR+''''
            SET @SQL=@SQL+' AND T1.ROWID IN '
            SET @SQL=@SQL+CHAR(13)+REPLICATE(' ',3)+'('
      END

      ELSE
      BEGIN
      IF LEN(@STR)=3
            BEGIN  --SET @STR=@STR+'%'
            SET @COUNTER=@COUNTER+1
                  SET @LASTSQL=''
                  SET @LASTSQL=@LASTSQL+CHAR(13)+REPLICATE(' ',@COUNTER*3)+'SELECT T'+CONVERT(VARCHAR,@COUNTER) +'.ROWID FROM CUSTOMER_TCNR_TRIGRAM T'+CONVERT(VARCHAR,@COUNTER)
                  SET @LASTSQL=@LASTSQL+' WHERE T'+CONVERT(VARCHAR,@COUNTER) +'.SEQ>T'+CONVERT(VARCHAR,@COUNTER-1) +'.SEQ AND TrIgram LIKE '''+@STR+''''
                  SET @LASTSQL=@LASTSQL+' AND T'+CONVERT(VARCHAR,@COUNTER) +'.ROWID IN '
                  SET @LASTSQL=@LASTSQL+CHAR(13)+REPLICATE(' ',@COUNTER*3)+'('
                  SET @SQL=@SQL+CHAR(13)+@LASTSQL
            END
      END
      SET @I=@I+1
      FETCH NEXT FROM CRS INTO @STR
END

DECLARE @LASTSQLTMP AS NVARCHAR(MAX)=@LASTSQL
DECLARE @POS AS INT=CHARINDEX('AND',@LASTSQLTMP)
SET @LASTSQLTMP=SUBSTRING(@LASTSQLTMP,1,@POS-1)
 SET @SQL=REPLACE(@SQL,@LASTSQL,@LASTSQLTMP)

SET @I=1
WHILE @I<@COUNTER
BEGIN
      SET @SQL=@SQL+CHAR(13)+REPLICATE(' ',(@COUNTER-(@I+1))*3)+')'
SET @I=@I+1 
END

SET @SQL=@SQL+';'
SET @SQL=@SQL+CHAR(13)+'SELECT'
SET @SQL=@SQL+CHAR(13)+'NAME_+ '' ''+SURNAME AS NAMESURNAME,TELNR'
SET @SQL=@SQL+CHAR(13)+'FROM CUSTOMERS WHERE ID IN (SELECT ROWID FROM #T)'
SET @SQL=@SQL+CHAR(13)+'DROP TABLE #T'
-- SET @SQL=@SQL+')'

PRINT @SQL
CLOSE CRS
DEALLOCATE CRS
 --SELECT @SQL
 EXEC SP_EXECUTESQL @SQL
DECLARE @DIFF AS INT
SET @DIFF=DATEDIFF(MILLISECOND,@DATE,GETDATE())
DECLARE @SECOND AS INT
DECLARE @MS AS INT=@DIFF
SET @SECOND =@DIFF/1000
SET @MS=@MS-@SECOND*1000
DECLARE @RESULT AS VARCHAR(100)
IF (@SECOND)<10>       SET @RESULT='00:00:0'+CONVERT(VARCHAR,@SECOND)
ELSE
SET @RESULT='00:00:'+CONVERT(VARCHAR,@SECOND)
IF (@MS)<10>       SET @RESULT=@RESULT+' 00'+CONVERT(VARCHAR,@MS)
IF (@MS)BETWEEN 10 AND 99
      SET @RESULT=@RESULT+' 0'+CONVERT(VARCHAR,@MS)
IF (@MS)BETWEEN 100 AND 999
      SET @RESULT=@RESULT+' '+CONVERT(VARCHAR,@MS)
SELECT @RESULT AS RESULT, (@SECOND*1000)+@MS AS MS

Bunun dinamik bir SQL cümlesi oluşturduğunu söylemiştik.

Bu sorguyu çalıştırdığımızda elde ettiğimiz sonuç da aynı. Burada ben sorguda neyin ne işe yaradığını bu yazıda anlatmak istemiyorum. Sorguyu doğrudan paylaşayım, siz yorumlayın.

Şimdi de aynı anda birden fazla sorgu ile trigram arama algoritmamızı deneyelim. Bakalım likea göre ne kadar performans kazanmışız.

Görüldüğü gibi aynı anda 10 oturumdan rastgele arama gerçekleştiriliyor ve ortalama sorgu süresi 150-200 milisaniye arasında değişiyor. Ne dersiniz? Çok iyi değil mi?

CPU kullanımına bakalım bir de. Gördüğünüz gibi gayet güzel bir değer. Like ile aradığımızda 99%’u görmüştük.

Buraya yazının başında paylaştığımız ve like ile aradığımız halini de koyalım ve ne kadar performans kazandığımızı tekrar bir görelim.

Normal like ile aradığımızda elde ettiğimiz ortalama süre 20 saniye civarında. Şimdi siz söyleyin. 20 saniye nere, 150 milisaniye nere?

Peki bir like araması için bu kadar zahmete değer mi? Buna siz karar verin. Eğer bu denli kritik bir uygulamanız varsa bence kesinlikle değer.

Peki customers tablomuzda bir güncelleme olduğunda ne olacak? Bunun için de basit bir trigger yazarak tablodaki bir satırda bir değişiklik olduğunda trigram tablosuna otomatik olarak insert gerçekleştirebilirsiniz.

Bu yazıda kullandığım veritabanını bağlantıdan indirebilirsiniz.

SQL hakkında daha geniş kapsamlı bilgiye erişmek, kariyerinizde bilginizle fark yaratmak isterseniz Miuul'un sunduğu MS SQL Developer eğitimine göz atabilirsiniz.