Re: bitstring ya da numerik tur uzerinde "bit count" alabilmek

On 12/4/06, Volkan YAZICI <yazicivo(at)ttnet(dot)net(dot)tr> wrote:
> On Dec 04 06:08, Kerem Hadimli wrote:
> > Karsilastirilacak olan veri, eldeki urunlerin ozelikleri ile [tabloda
> > varolan veriler], musterinin beklentisi, aradigi urunun ozellikleri
> > (yani, "aradigim urunde A C D ozellikleri benim icin onemli, B E F G
> > ozellikleri farketmez" demesi musterinin)
> >
> > Yapmak istedigim sey, yukaridaki ornekten devam ederek, elde A C D
> > ozellikleri olan urun olmasa bile, "bakin, en basta A D ozelligi olan
> > su urun var, ayrica isterseniz C D ozelligi olan su urun var, daha
> > sonra sadece A ozelligi olan su urun var" diye bir siralama
> > koyabilmek.
>
> O zaman elimizdeki veri şöyle bir şey: 01001...1010 (300 haneli),
> ve farzedelim ki yapılacak arama 10110000...000 (İlk 4 özellği A, B,
> C, D olarak aldım.) Şimdi yapmamız gereken tek şey sorguyu şu şekilde
> sıralamak:
>
> SELECT ...
> FROM urunler
> WHERE flags & 10110000...0000 = 1011000...0000 OR -- A, C, D için
> ((flags | 1011) >> 296) <> 0 -- A veya C veya D için
> ORDER BY ((flags | 1011) >> 296)
>
> -- Yukarıdaki 296 = 300 - 4'ten geliyor. Buradaki 4 ise, sadece ilk
> -- 4 alan (A, B, C, D ile ilgilenmemizden kaynaklı.) Bu sorgu ister
> -- veritabanına gömülü IMMUTABLE bir fonksiyon tarafından,
> -- istenirse uygulama arayüzü tarafından verilen flag'lar için
> -- otomatik olarak üretilebilir.
>
> Eğer sorunuzu doğru anladıysam, bunun istediğiniz ürünleri ilgili
> öncelik sırasına göre doğru olarak döndürmesi lazım. Yani >> (right
> shifthing) sayının içindeki bitleri saymaktan çok daha iyi bir
> yöntem ve istediğiniz öncelik sırasını da koruyur gibime geliyor.
>
Sanirim yanlis anlasilabilecek bir ornek verdim. ORDER BY <bitstring>
yaptigimiz zaman, A'ya, B'den daha fazla oncelik veriliyor, halbuki
elimdeki durumda A ile B nin birbirlerine gore onceligi yok (yani,
kullanicinin A C D istegine uygun bulunan sonuclarda, A C ile C D nin
siralamasinin onemi yok, ama tek basina A 'nin, A C 'den de C D 'den
de sonra gelecegi kesin)

> Şimdi gelelim bu (ya da buna benzer bir) sorgunun nasıl yoğun kullanım
> altında sunucuyu dar boğaza sokmayacağına. Ben olsam ilk önce doğru
> noktalara INDEX'ler koyardım. Fakat şu da unutulmamalı ki, INDEX'ler
> SELECT'lerde başarım artışı sağlayabilecek olurken (ki bu her zaman
> kesin değildir), INSERT/UPDATE işlemlerinde de yavaşlayama sebebiyet
> verir (ki bu kesindir). Yani aşağı tükürsem sakal, yukarı tükürsem
> bıyık durumu. İkisinin ortasını bulmanız lazım.

>Ek olarak, veriniz
> bana parçalanabilir gibi geliyor. (PostgreSQL dökümantasyonundaki
> partitioning kısmına bir göz atın.) Veriyi doğru şekilde RAM'e
> sığabilen tablolara dağıtabilirseniz süper olur.

>
> > Ayni yazilimin birden fazla yerde kullanilacak olmasi, ve bu
> > ozelliklerin dinamik olmasi ihtiyaciyla, en uygun cozumu urun
> > ozelliklerini bitstring (bit(n) sanirim) olarak saklayarak, musterinin
> > istegi olan bitstring'le ANDlemek olarak goruyorum (dinamik'le kastim,
> > (ucta bir ihtiyac olmadikca) kullanim esnasinda degil, ama ilk kurulum
> > esnasinda program yapisi / queryler / veritabani yapisini degistirmeye
> > gerek kalmadan ozellestirilebilmesi).
> >
> > Dedigim gibi, ilk asamada, bitstring uzerinden "kac bitin degeri var"
> > bilgisini almaya yonelik bir sey bulamadigim icin, kalan kisimda
> > gecikme yasamamak icin bitstring'i ayri ayri boolean'larla
> > gerceklestirdim, bu degisecek haliyle, 10 urunde test edilebiliyor,
> > 1000 urun bile olsa sunucunun gereksiz yere cok fazla efor sarfedecegi
> > garanti, ama degismesi icin, ayni fonksiyonelligin saglanmasi
> > gerekiyor :)
> >
> > okudugum bitcount metinlerinde, 16bitlik onceden hesaplanmis
> > tablolardan yapilan sayma isleminin cok da yavas olmadigini gordum,
> > zaten tek tek toplama yapmak istemiyorum. Bu yuzden C ile bir eklenti
> > fonksiyon yapilabilir diye dusunuyorum, ama daha uygun bir oneri varsa
> > tercih ederim tabii ki :) sonucta 3000 degil, 300 alana ihtiyacim
> > oldugu icin, her 16 alanin bit sayisini, onceden hesaplanmis bir
> > tablodan a[deger] olarak cekmek mumkun, 320 alan icin 20 adet integer
> > toplamasi eder bu da, makul gorunuyor. Ornegin, eleman basina,
> > collation kullanan bir string siralamasindan daha kotu performans
> > vermeyecegini dusunuyorum; karsilastirmak icin yapilan overhead icin
> > iyi bir ornek olabilir :)
>
> Bence bu bit sayma benzeri işlemler için IMMUTABLE bir prosedür
> oluşturup (C olmak zorunda değil), bunun üzerinden INDEX'leme
> yapın. (Ayrı bir alanda saklamak da bir çözüm. Ama burada asıl anahtar
> IMMUTABLE bir fonksiyon kullanmanız gerektiği.)

Immutable hakkinda dokumantasyonu okudum, kesinlikle kullanmam gereken
bir seymis :)

Index'leme (ve aslinda, buna bagli olarak partitioning) kisminda,
kullanicidan gelecek arama kriterleri belirsizken, bu ozelliklerden
faydalanmam mumkun mu?

Sonucta, bitsayisi(urun ozellikleri) uzerinden indeksleme yapilabilir
(bitsayisi(x) immutable ve dedigimiz bit sayma islemini yapan bir
fonksiyon), fakat siralamalar, kullanicinin istegine uygunluk
acisindan oldugu icin, bitsayisi(urun ozellikleri & istek) 'e gore bir
indeksleme yapmak, istek belirsiz oldugu icin mumkun gorunmuyor. Bunun
nasil bir cikisi olabilir (belki, tum isteklere gore olmasa bile
gelebilecek potansiyel isteklere gore optimizasyon saglayabilecek
assumptionlar kullanarak) ?

>
> Şimdilik aklıma gelenler bunlar. Siz ölçün tartın, yine tartışalım.
>
>
> İyi çalışmalar.
>

cok tesekkur ederim,
Kerem HADIMLI