التعقيد الزمني لوظائف SQL المضمنة مثل المجموع والعدد والمتوسط

Question

ما هو التعقيد الزمني لوظيفة مثل العد أو المجموع أو المتوسط ​​أو أي من وظائف "الرياضيات" المضمنة في الخلية وخادم SQL وأوراكل وغيرها؟

قد يعتقد المرء أن استدعاء المبلغ (myColumn) سيكون خطيًا.

لكن العدد (1) ليس كذلك.كيف يحدث ذلك وما هو التعقيد الزمني الحقيقي؟

في عالم مثالي، أريد أن يكون المجموع والمتوسط ​​والعد هو O(1).لكننا لا نعيش في واحدة من تلك، أليس كذلك؟

Answer 1

في SQL، يعد تعقيد دالة الرياضيات للمجاميع غير ذي صلة تمامًا.الشيء الوحيد المهم حقًا هو تعقيد الوصول إلى البيانات:ما هو مسار الوصول الذي تم اختياره (مسح الجدول، مسح نطاق الفهرس، البحث عن الفهرس وما إلى ذلك) وعدد الصفحات التي تمت قراءتها.قد تكون هناك اختلافات طفيفة في الأجزاء الداخلية لكل تجميع، ولكنها جميعًا تعمل بنفس الطريقة تقريبًا (استمر في تشغيل الحالة وحساب التجميع قيد التشغيل لكل قيمة إدخال) وهناك بالتأكيد اختلافات لا التجميعي الذي ينظر إلى الإدخال مرتين، لذا فكلهم O(n) كتنفيذ داخلي، حيث 'n' هو عدد السجلات التي يتم تغذيتها للتجميع (وليس بالضرورة عدد السجلات في الجدول!).

تحتوي بعض المجاميع على اختصارات داخلية، على سبيل المثال.عدد(*) يمكن قم بإرجاع العدد من البيانات التعريفية في بعض الأنظمة، إن أمكن.

Answer 2

ما هو التعقيد الزمني لوظيفة مثل العد أو المجموع أو المتوسط ​​أو أي من وظائف "الرياضيات" المضمنة في الخلية وخادم SQL وأوراكل وغيرها؟

• في MySQL مع MyISAM, COUNT(*) بدون GROUP BY يكون O(1) (ثابت)

  يتم تخزينه في البيانات الوصفية للجدول.

• في جميع الأنظمة، MAX و MIN على التعبيرات المفهرسة دون GROUP BY نكون O(log(n)) (لوغاريتمي).

  يتم جلبها باستخدام فهرس واحد.

• الوظائف الإجمالية هي O(n) (خطي)، عند استخدامه بدون GROUP BY أو GROUP BY الاستخدامات HASH

• الوظائف الإجمالية هي O(n log(n)) متى GROUP BY الاستخدامات SORT.

يجب جلب جميع القيم وحسابها وتخزينها في متغيرات الحالة (والتي يمكن تخزينها في جدول التجزئة).

وبالإضافة إلى ذلك، عند استخدام SORT, ، ينبغي أيضًا فرزها.

Answer 3

ملحوظة:هذه تكهنات مبنية على فهمي لكيفية عمل مخططي استعلام SQL، وقد لا تكون دقيقة تمامًا.

أعتقد أن جميع الوظائف المجمعة، أو على الأقل تلك "الرياضية" التي ذكرتها أعلاه، يجب أن تكون O(n).سيتم تنفيذ الاستعلام تقريبًا كما يلي:

1. جلب الصفوف المطابقة لمسندات الربط ومسندات التصفية (أي "جملة WHERE")
2. قم بإنشاء مجموعات الصفوف وفقًا لجملة GROUP BY.يتم إنشاء مجموعة صفوف واحدة للاستعلامات التي لا تحتوي على GROUP BY
3. لكل مجموعة صفوف، قم بتطبيق الدالة التجميعية على الصفوف الموجودة في المجموعة.بالنسبة لأشياء مثل SUM وAVG وMIN وMAX بالإضافة إلى الوظائف غير الرقمية مثل CONCAT، توجد خوارزميات O(n) بسيطة، وأظن أنه يتم استخدامها.قم بإنشاء صف واحد في مجموعة الإخراج لكل مجموعة صفوف تم إنشاؤها في الخطوة رقم 2
4. في حالة وجود مسند HAVING، قم بتصفية صفوف الإخراج باستخدام هذا المسند

ومع ذلك، لاحظ أنه على الرغم من أن الوظائف المجمعة هي O(n)، فقد لا تكون العملية كذلك.إذا قمت بإنشاء استعلام عن الديكارتي الذي يربط الجدول بنفسه، فسوف تنظر إلى الحد الأدنى O(n*n) فقط لإنشاء مجموعة الصفوف الأولية (الخطوة رقم 1).قد يكون الفرز لإنشاء مجموعات صفوف (الخطوة رقم 2) هو O(n lg n)، وقد يتطلب تخزينًا على القرص لعملية الفرز (على عكس عملية الذاكرة فقط)، لذلك قد يظل أداء الاستعلام الخاص بك ضعيفًا إذا كنت التعامل مع العديد من الصفوف.

Answer 4

بالنسبة للاستعلامات الخاصة بنمط مستودع البيانات الضخمة، يمكن لقواعد البيانات الرئيسية أن توازي المهمة، بحيث تعمل عليها وحدات معالجة مركزية متعددة.لذلك ستكون هناك نقاط عتبة حيث لا تكون خطية تمامًا حيث أن تكلفة تنسيق الخيوط المتوازية تتعارض مع فائدة استخدام وحدات المعالجة المركزية المتعددة.