بحث سريع بدون فهرس

مشكلة

لدينا جميعًا أيام عمل عندما يأتي إلينا شخص ما بمتطلب مستحيل حقًا يتطلب معجزة لتحقيقه. حدثت حالتي عندما جاءني أحد زملاء التسويق بسؤال يبدو بسيطًا: إذا كان بإمكاني الحصول على بيانات من جدول واحد لشهر معين قبل عامين. لا بأس ، يمكنك القول ، لكنني تذكرت بشكل غامض أن الطاولة كانت كبيرة جدًا. يحتوي الجدول على حقل وقت ووقت الإنشاء ، ولكن هل كان هناك فهرس في هذا الحقل؟



بالطبع ، أرادوا أيضًا الحصول على البيانات بسرعة. كالعادة ، قلت ، "سأرى ما يمكنني القيام به" ، وذهبت لإلقاء نظرة فاحصة على الجدول قيد المناقشة. حظا سعيدا لن يتركنا أبدا ، والفهرس غير موجود حقا ، والجدول كان كبيرا. ليست مشكلة ، يمكننا مسح الطاولة ، أليس كذلك؟ خطأ. إذا تعلمت أي شيء من سنوات العمل مع قواعد البيانات ، فهذا الحجم مهم. سيكون جدولًا يحتوي على مئات الملايين من السجلات ، التي تتكون من عدة أعمدة صحيحة ، هائلة للغاية. ثم قم بإضافة أعمدة varchar و datetime مختلفة. الآن هذا تحدٍ حقيقي ، أليس كذلك؟



الجدول الذي كنت أنظر إليه يحتوي على مليار سجل ، حرفيا. يمكن أن يستغرق مسح الجدول البسيط أكثر من يوم بسهولة وكنت بحاجة إلى معالجة البيانات المستخرجة أيضًا. بالإضافة إلى ذلك ، قد لا يكون مسح جدول بهذا الحجم مفيدًا للصحة العامة للنظام كما يبدو للوهلة الأولى. يجب استخراج جميع الصفحات الممسوحة ضوئيًا من الأقراص في ذاكرة خادم SQL عن طريق ملؤها. سيؤدي هذا بدوره إلى إلغاء تحميل صفحات البيانات من ذاكرة التخزين المؤقت ، والتي يمكن استخدامها للمهام التشغيلية الحالية. قد تنتظر طلبات المستخدمين الحالية لفترة أطول بينما يقوم الخادم بإعادة قراءة البيانات من الأقراص ، بدلاً من إعادة استخدام صفحات البيانات من الذاكرة بسرعة. يمكن أن ينخفض ​​الأداء ، وفي أسوأ الحالات ، يمكن أن يركع الخادم بشكل كامل. وهكذا ،عند مسح جدول ، يجب عليك استخدام تقنية خاصة - تشغيله على دفعات صغيرة ، مع الحفاظ على الوضع الحالي والنتائج المتوسطة في مكان ما. يسمح هذا الأسلوب للخادم بإعادة التكوين والاستراحة دون السماح بضربة أداء كبيرة.



وهكذا ، كنت أفكر في السيناريو وأقيم الوقت الذي ستستغرقه لتشغيل البرنامج النصي وتنفيذه عندما حدث لي أن قيم التاريخ ووقت الإنشاء كانت مرتبطة بمعرف الجدول. كان المعرف (ID) عمودًا من القيم المتزايدة باستمرار ومفتاحًا أساسيًا يعتمد عليه. عند التحديد بواسطة المعرف ، تم فرز قيم التاريخ والوقت بشكل طبيعي مسبقًا بنفس طريقة قيم المعرف. انتظر ، فكرت ، يمكنني تنفيذ شيء سريع للغاية من فحص الطاولة ، وهو شيء في أسوأ الحالات لن يستغرق سوى 30 خطوة بدلاً من 500.000.000! بحث ثنائي!

بحث

بالنسبة لكل شخص تخرج مثلي من التدريب منذ فترة طويلة ، يجب أن يكون التدريب النظري في ترتيب الأشياء. البحث الثنائي هو طريقة بسيطة ولكنها فعالة للغاية للبحث عن قيمة في مصفوفة مرتبة (في حالتنا ، في عمود جدول). يجب أن يكون الصفيف مرتبًا مسبقًا ومحدودًا. يتم البحث من خلال مقارنة العنصر الأوسط من الصفيف الخاص بك مع الهدف. إذا كانوا متساوين ، فإن البحث قد انتهى. إذا لم يكن الأمر كذلك ، فإنك تحذف النصف الذي يكون فيه العنصر المطلوب غائبًا بوضوح ، وتكرر الخطوة السابقة حتى يتبقى واحد فقط. ابحث عن الوسط ، قارن الهدف به ، إذا لم يكن متساويًا ، قم بإزالة النصف مرة أخرى وهكذا. العدد الإجمالي للخطوات المطلوبة للعثور على الهدف في أسوأ الحالات ، عندما تجده في الخطوة الأخيرة ، هو log (N) ، حيث N هو عدد العناصر. قارن هذا بـ N / 2 ،عندما تقوم فقط بالتكرار على المصفوفة. بشكل عام ، سيكون N ، ولكن إذا استطعنا تخمين ما إذا كان الهدف أقرب إلى النهاية ، فيمكننا العودة ، وبالتالي تقليل العدد الإجمالي للخطوات المطلوبة.



في حالتي ، N = 1،000،000،000 وهكذا توصلت إلى الرقمين أعلاه: 30 و 500،000،000. سوف يلعب المعرف دور عد صفيف ، ويكون تاريخ ووقت الإنشاء هو قيمة عنصر الصفيف. ومع ذلك ، هناك تحذير واحد. عد صفيف ، بحكم تعريفه ، هو تسلسل متجاور من الأعداد الصحيحة. يمكن أن تكون هناك مسافات في معرفات الجدول بسهولة بسبب حذف سجل أو إعادة ملء معرف. تعريف بسيط للوسط بقسمة نطاق المعرفات على 2 ، يجب ألا تتوقع أنه سيكون هناك سجل بمثل هذا المعرف. بدلاً من البحث المباشر ، كان عليّ استخدام الدالة top (). شئ مثل هذا:

Select top(1) * from Table where id <= @id order by id desc

استخدمت "<=" و "تنازلي" لأنني أردت العثور على قيمة إما مساوية للهدف أو قبله مباشرة. بشرط أن يكونl ، و @ r ، حدودًا يمنى ويسرى على التواليهوية شخصية هو الوسط ،dt هو وقت الإنشاء (تاريخ الإنشاء) ، التوقيت الصيفي هو الهدف و هوية شخصيةr هو معرّف الجدول الحقيقي (ID) ، قد تبدو الخوارزمية كما يلي:

while @l <@r

begin

    --  

    @id = @l +floor((@r-@l)/2)

    --    

    select top(1) @idr = id, @dt = creation_datetime from Table where id <= @id order by id desc

    --  

    if(@dt<@tdt)

        @l = @id +1

    else

        @r = @id

end 

وجدت آخر هوية شخصيةص سيكون معرف الدخول بعد ذلك هناك حاجة. تحتوي الخوارزمية على نوع من الإزاحة "اليسرى" ، أي ميل إلى اختيار أقصى اليسار من جميع القيم. نظرًا لأنني أردت أن يكون السجل مع القيمة قريبة من الهدف قدر الإمكان ، فقد تحققت أيضًا من أقرب الجيران الأيمن والأيسر في الجدول لمعرفة ما إذا كان أحدهما أفضل. يرجى ملاحظة أنني لم أستخدم المعرّف الحقيقي من الجدول لعملية التكرار ، كما هو الحال في هذه الحالة ، مع وجود مسافات في قيم المعرّف ، وفي بعض الحالات ، يمكن أن تدخل الخوارزمية في حلقة لا نهائية.



استغرق كتابة النص واختباره حوالي ساعة. باستخدامه ، وجدت الإدخال الأول مع تاريخ ووقت إنشاء محددين. بعد ذلك ، استخدمت عبارة تحديد بسيطة تحتوي على شرط حيث يحتوي على الشرطين: id> = @ و create_datetime> = @ dt1 و create_datetime <@ dt2. كنت بحاجة فقط للتأكد من أن المحسن سيختار استخدام مفتاح أساسي بدلاً من فهرس أو مسح جدول. بشكل عام ، لقد فعلت ذلك في أقل من ساعتين! كان من المفاجئ إعادة اكتشاف أن الخوارزميات ليست شيئًا باطنيًا مدفونًا عميقًا داخل خادم sql ، بل شيئًا يمكن استخدامه بسهولة في العمل اليومي.



فيما يلي النص الكامل الذي كتبته. يرجى الاطلاع على التعليقات في الداخل لفهم كيفية استخدامه.

/* 
         
      ,     . 
     ,   datetime  3 
*/
--  ,  ,       
declare @debug bit = 0
-- @Table -  ,     .
declare @Table varchar(128) = 'TableX' 
-- @Id -    (id)   
declare @ID varchar(128) = 'Id' 
-- @DateTimeColumn -   datetime      
declare @DateTimeColumn varchar(128) = 'created_dt'
--      
declare @TargetDateTime datetime = '2020-01-03 18:23:03'
declare @Sql varchar(max)
set @sql = '
--    
declare @debug bit = <debug>
--    
declare @tdt datetime = ''<TargetDateTime>''
--        ( ) 
declare @id bigint 
--       
declare @l bigint, @r bigint
--  ,        , datetime    
declare @dt datetime, @idr bigint
--   «»  «» 
select @l = min(<ID>), @r = max(<ID>) from <Table>
while @l < @r
begin
    --  
    set @id = @l +floor((@r-@l)/2)
    --     
    select top(1) @dt = <DateTimeColumn>, @idr = <ID> from <Table> where <ID> <= @id order by <ID> desc
    --   ,   
    if( @debug = 1 )
    begin
        select ''@id'' = @id, ''@l'' = @l, ''@r'' = @r, ''@dt'' = @dt, ''@idr'' = @idr
    end
    if(@dt < @tdt)
        set @l = @id +1
    else
        set @r = @id
end
-- ,       
declare @t table(id bigint, dt datetime, dlt float)
insert @t(id, dt, dlt)
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float)) 
  from <Table> 
 where <ID> < @idr 
order by <ID> desc
insert @t(id, dt, dlt) 
select top(1) <ID>, <DateTimeColumn>, abs(cast(<DateTimeColumn> as float) -cast(@tdt as float)) 
  from <Table> 
 where <ID> > @idr 
order by <ID>
insert @t(id, dt, dlt) 
select @idr, @dt, abs(cast(@dt as float) -cast(@tdt as float))
select top(1) @dt = dt, @idr = id from @t order by dlt, id 
select ''Found Value'' = @dt, ''Record Id'' = @idr
'
set @sql = replace(
            replace(
             replace(
              replace(
               replace(@sql, '<ID>', @ID), 
              '<Table>', @Table), 
             '<TargetDateTime>', convert(varchar(50), @TargetDateTime, 121)),
            '<debug>', @debug),
           '<DateTimeColumn>', @DateTimeColumn)
exec (@sql)