Многобазово криптиране на големи релации Ако размера на блока е в байта, а в основната памет имаме М

Ако размера на блока е В байта, а в основната памет имаме М байта за буфериране, а записите са по R байта. Броя на блоковете М/В един за извеждане останалите – броя подсписъци, които ще бъдат сливани. Т.е. при първата фаза могат да бъдат създадени М/В-1 списъка т.е. имаме М пъти зареждане на блокове в ОП със записи за сортировка. Всеки път когато зареждаме ОП сортираме М/R записи. Всеки запис, който може да сортираме е M/Rx(M/B-1)=M/RB.

Двуфазната сортировка е малко вероятно да превиши 0,67 терабайта и затова в СУБД се използва тя.

Ускоряване на достъпа до вторичната памет

Когато системата изпълнява голям брой заявки едновременно изборът на блокове е случаен. Ако сортировката е на голяма релация голяма част от времето се заема от релацията и може да се възползваме от начина, по който са разположени дисковете и да оптимизираме достъпа до вторичната памет. Когато 1 система е натоварена с голям брой несвързани заявки можем да се стремим да увеличим пропускателната способност на системата (да отложим някои заявки) или да бързаме да изпълним всички заявки на опашката. Прилагат се няколко стратегии:

1. 
   Поставяме блоковете, върху които едновременно се прави достъп на един цилиндър – избягваме търсенето и латентността от въртенето. Времето за търсене на цилиндър е половината от времето за достъп до блок. Има приложения, в които е смислено така да се съхраняват данните, че лесно да се прави достъп до тях – релациите да се разполагат на отделни цилиндри. Ако един цилиндър не стига за дадена релация се използват два съседни. Времето за прочитане на данните от една писта или цилиндър – игнорираме всичко, освен първото време за търсене (до придвижването до цилиндъра) и първата ротационна латентност (изчакване на първият блок да се придвижи под главата). Така можем да достигнем максимална скорост за прехвърляне на данни от диска към паметта и обратно.
   
2. 
   Разделяме данните върху няколко малки диска – разполагаме с повече блокови глави и това увеличава броя блокове, които можем да обработим за единица време. При използването на няколко диска игнорираме времето на работа на дисковият контролер, шина, ОП. Ако дисковете са 4 по-малки данните върху съседните цилиндри разпределяме върху тях. В първата фаза при зареждане в ОП всеки диск ползва по ¼ от буферите – времето за търсене е пренебрежимо малко, както и времето за латентност. Прочитането става за по-малко време. В първа фаза се разпределя всеки сортиран подсписък върху четирите диска. Записът също се извършва едновременно, т.е. е 4 пъти по-бърз. Във втора фаза отново няма преимущество. Може да се програмира така, че сравненията да продължат веднага след като е прочетен първият елемент, но не е препоръчително. Ако се прилага този подход има възможност във втора фаза да се съкрати времето за запис. Може да се ускори записът във втора фаза ако големият буфер се раздели на 4 и когато се пълни един от тях другите три се използват за записване. В някои случаи втора фаза се ускорява 2-3 пъти.
   
3. 
   Създаване на огледани дискове – на данните се правят копия върху два или повече диска – пак разполагаме с няколко блокови глави и при провал в някои от дисковете имаме информацията запазена. Огледалните дискове могат да се използват за ускоряване на достъпа до данните. Във втора фаза можем да уредим зареждането на 4 блока от 4 различни сортирани списъка, чиито блокове са празни. Не може да избираме от кои 4 списъка ще се четат нови блокове. Ако разполагаме с 4 копия на големия диск можем да гарантираме, че системата ще чете 4 блока едновременно. Винаги може да се определи от кой диск ще се проведе следващото четене. Не ускорява записа, но не го и намаля, ако го сравняваме със използването на един диск. Това е така, защото когато трябва да запишем блок ние го пишем на всички дискове, които имат копие. Тъй като писането може да е паралелно, времето за писане остава същото като това за писане на един диск, а има малка възможност за различа при времето за писане за различните огледални дискове, защото не можем да разчитаме на тях да се въртят абсолютно синхронно. Но тези разлики в ротационната латентност са приблизителни и ако използваме първата стратегия могат да се игнорират.
   
4. 
   Прилагане на алгоритъм за режимно използване на диска – може да се реализира в ОС, СУБД, контролера на диска. Определя реда, по който се изпълняват заявките, за да могат няколко блока да бъдат едновременно четени или писани. Този алгоритъм не е полезен, когато системата трябва да чете или пише блокове в определен ред. Но когато системата поддържа много малки процеси, всеки от които има достъп до няколко блока, може да се увеличи бързодействието като се избере кой процес да е първи. Алгоритъм на асансьора – за ускоряване на достъпа до диска. Когато главите преминават над цилиндър спират ако има една или повече заявки за блокове на този цилиндър. Тези блокове се четат или пишат , както е изискано, след това главите продължават в същата посока до следващия цилиндър, когато главите стигнат позиция, където няма повече заявки напред те обръщат посоката. В контролера са се натрупали заявки и той определя режима на изпълнението им, преподрежда ги. Не е полезно когато системата прави сортировка (пише блокове), защото има система по какъв начин да се подредени. Алгоритъм на асансьора – ефекта е, че пропускателната способност на диска се увеличава. Времето за търсене се минимизира, а времето за латентност остава същото. Бързодействието на изпълнение на заявките пада.
   

5. 
   Предварително зареждане на блокове в ОП като се прогнозира тяхната по-късна употреба. Поне за известно време системата е заета с определена задача (например сортировка). Бързодействието на системата и използването на вторичната памет може да се определи по два начина: а)Какво ще се случи ако има голям брой процеси, поддържани едновременно от компютърната система б)Ако има фиксиран бюджет на компютърната система или върху нея се изпълнява смес от различни заявки. Предварително зареждане (двойно буфериране) – по-добре режимираме диска и ако ползваме алгоритъма на асансьора може да намалим времето за достъп до блоковете.
   

1. 
   когато блоковете се четат и пишат в предсказуем във времето ред от един процес. Отлична за приложения, при които има предсказуем достъп до диска.
   
2. 
   когато имаме много процеси, които са кратки и генерират случаен достъп до диска. Имаме множество дискове – и в двата случая ще се увеличи бързодействието до 2-3 пъти. За съжаление четене и писане върху един диск не могат да се извършат едновременно. Цената на няколко малки диска е по-голяма от един голям със същия капацитет.
   

При алгоритъма на асансьора се намаля средното време за четене и писане на блокове, най-ефективен е когато има много заявки, но тези процеси, които чакат четенето и писането твърде много чакат.