Кіріспе
Реляциялық деректер базасында қолданылатын алгоритм. Сортталған біріктіру (merge join) – біріктіру алгоритмі және реляциялық деректерді басқару жүйесін іске асыруда қолданылады. Біріктіру алгоритмінің негізгі міндеті – әрбір біріктіру атрибутының ерекше мәні үшін, әрбір қатынаста сол мәнді көрсететін түйіндер жиынын табу. Сортталған біріктіру алгоритмінің негізгі идеясы – ең алдымен қатынастарды біріктіру атрибуты бойынша сұрыптау, сонда бірімен бірі кезегімен жүретін сызықтық сканерлеулер осы жиындарды бір уақытта кездестіреді. Іс жүзінде, сортталған біріктіруді орындаудың ең қымбат бөлігі – алгоритмге берілетін екі кірісті де сұрыпталған күйде ұйымдастыру болып табылады. Бұл нақты сұрыптау операциясы (көбінесе сыртқы сұрыптау) арқылы немесе біріктіру қатынастарының бірінде немесе екеуінде бұрыннан бар реттіліктерді пайдалану арқылы жүзеге асырылуы мүмкін. Соңғы жағдай, «қызықты реттілік» деп аталады, себебі біріктіруге берілетін кіріс, ағаш негізделген индекстің сканерлеуінен, басқа сортталған біріктіруден немесе тиісті кілт бойынша сұрыпталған нәтиже беретін басқа жоспар операторынан туындауы мүмкін. Қызықты реттіліктер міндетті түрде кездейсоқ болуы керек емес: оптимизатор осы мүмкіндікті іздеп, егер бір немесе бірнеше төменгі деңгейдегі түйіндер пайдалана алатын қызықты реттілік пайда болса, нақты алдыңғы операция үшін оңтайлы емес жоспарды таңдауы мүмкін.
The sort merge join (also known as merge join) is a join algorithm and is used in the implementation of a relational database management system. The basic problem of a join algorithm is to find, for each distinct value of the join attribute, the set of tuples in each relation which display that value. The key idea of the sort merge algorithm is to first sort the relations by the join attribute, so that interleaved linear scans will encounter these sets at the same time. In practice, the most expensive part of performing a sort merge join is arranging for both inputs to the algorithm to be presented in sorted order. This can be achieved via an explicit sort operation (often an external sort), or by taking advantage of a pre existing ordering in one or both of the join relations. The latter condition, called interesting order, can occur because an input to the join might be produced by an index scan of a tree based index, another merge join, or some other plan operator that happens to produce output sorted on an appropriate key. Interesting orders need not be serendipitous: the optimizer may seek out this possibility and choose a plan that is suboptimal for a specific preceding operation if it yields an interesting order that one or more downstream nodes can exploit.
Күрделілігі
Let және be қатынастары, онда жады мен жадының беттеріне сыяды. Ең нашар жағдайда, сұрыптау-біріктіру қосылымы I/O операцияларында жұмыс істейді. Егер және реттелмеген болса, ең нашар жағдайдағы уақыт шығыны сұрыптау уақытының қосымша мүшелерін қамтиды: , бұл тең (сызықтық-логарифмдік мүшелер сызықтық мүшелерден басым болғандықтан, Үлкен О нотациясын қараңыз – Көбінесе қолданылатын функциялардың реті).