Antipatterns PostgreSQL: A Tale of Iterative Refinement of Search by Name یا "بهینه سازی رفت و برگشت"

هزاران مدیر از دفاتر فروش در سراسر کشور رکورد می کنند سیستم CRM ما روزانه ده ها هزار مخاطب - حقایق ارتباط با مشتریان بالقوه یا موجود. و برای این، ابتدا باید مشتری پیدا کنید و ترجیحاً خیلی سریع. و این اغلب با نام اتفاق می افتد.

بنابراین، تعجب آور نیست که، یک بار دیگر پرس و جوهای "سنگین" را در یکی از بارگذاری شده ترین پایگاه های داده - خودمان تجزیه و تحلیل کنیم. حساب شرکتی VLSI، "در بالا" را پیدا کردم درخواست جستجوی "سریع" بر اساس نام برای کارت های سازمان

علاوه بر این، تحقیقات بیشتر نمونه جالبی را نشان داد ابتدا بهینه سازی و سپس کاهش عملکرد درخواست با پالایش متوالی آن توسط چندین تیم، که هر کدام تنها با بهترین نیت عمل کردند.

0: کاربر چه می خواست؟

[KDPV از این رو]

وقتی کاربر در مورد جستجوی «سریع» با نام صحبت می‌کند معمولاً به چه معناست؟ تقریباً هرگز معلوم نمی‌شود که جستجوی «صادقانه» برای زیررشته‌ای مانند ... LIKE '%роза%' - زیرا در این صورت نتیجه نه تنها شامل می شود 'Розалия' и 'Магазин Роза'اما 'Гроза' و حتی 'Дом Деда Мороза'.

کاربر در سطح روزمره فرض می کند که شما به او ارائه می دهید جستجو بر اساس آغاز کلمه در عنوان و آن را مرتبط تر کنید که شروع می شود وارد شد. و شما آن را انجام خواهید داد تقریباً فورا - برای ورودی بین خطی

1: کار را محدود کنید

و حتی بیشتر از آن، شخص به طور خاص وارد نخواهد شد 'роз магаз'، به طوری که باید هر کلمه را با پیشوند جستجو کنید. نه، پاسخ دادن به یک اشاره سریع برای آخرین کلمه برای کاربر بسیار ساده‌تر از این است که عمداً موارد قبلی را "کم مشخص" کند - ببینید هر موتور جستجوی چگونه این موضوع را مدیریت می کند.

به طور کلی، به درستی تدوین الزامات برای مشکل بیش از نیمی از راه حل است. گاهی اوقات تجزیه و تحلیل مورد استفاده دقیق می تواند به طور قابل توجهی بر نتیجه تأثیر بگذارد.

یک توسعه دهنده انتزاعی چه کاری انجام می دهد؟

1.0: موتور جستجوی خارجی

اوه ، جستجو دشوار است ، من اصلاً نمی خواهم کاری انجام دهم - بیایید آن را به devops بدهیم! به آنها اجازه دهید یک موتور جستجو در خارج از پایگاه داده مستقر کنند: Sphinx، ElasticSearch،...

یک گزینه کاری، هرچند کار فشرده از نظر هماهنگ سازی و سرعت تغییرات. اما در مورد ما نه، زیرا جستجو برای هر مشتری فقط در چارچوب داده های حساب او انجام می شود. و داده ها دارای تنوع نسبتاً بالایی هستند - و اگر مدیر اکنون کارت را وارد کرده باشد 'Магазин Роза'، پس از 5-10 ثانیه ممکن است قبلاً به خاطر بیاورد که فراموش کرده است ایمیل خود را در آنجا نشان دهد و می خواهد آن را پیدا کند و آن را اصلاح کند.

بنابراین - اجازه دهید جستجوی "مستقیم در پایگاه داده". خوشبختانه، PostgreSQL به ما اجازه می دهد این کار را انجام دهیم، و نه فقط یک گزینه - ما به آنها نگاه خواهیم کرد.

1.1: رشته فرعی "صادقانه".

ما به کلمه "زیر رشته" چسبیده ایم. اما برای جستجوی فهرست با زیر رشته (و حتی با عبارات منظم!) یک عالی وجود دارد ماژول pg_trgm! فقط در این صورت نیاز به مرتب سازی صحیح خواهد بود.

بیایید سعی کنیم صفحه زیر را برای ساده کردن مدل در نظر بگیریم:

CREATE TABLE firms(
  id
    serial
      PRIMARY KEY
, name
    text
);

ما 7.8 میلیون رکورد از سازمان های واقعی را در آنجا بارگذاری می کنیم و آنها را فهرست می کنیم:

CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

بیایید به دنبال 10 رکورد اول برای جستجوی بین خطی باشیم:

SELECT
  *
FROM
  firms
WHERE
  lower(name) ~ ('(^|s)' || 'роза')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
, lower(name) -- остальное по алфавиту
LIMIT 10;

[به توضیح.tensor.ru نگاه کنید]

خب، چنین ... 26 میلی‌ثانیه، 31 مگابایت خواندن داده ها و بیش از 1.7 هزار رکورد فیلتر شده - برای 10 مورد جستجو شده. هزینه های سربار خیلی زیاد است، آیا چیزی کارآمدتر وجود ندارد؟

1.2: جستجو بر اساس متن؟ FTS است!

در واقع، PostgreSQL بسیار قدرتمند است موتور جستجوی متن کامل (جستجوی متن کامل)، از جمله قابلیت جستجوی پیشوند. یک گزینه عالی، شما حتی نیازی به نصب برنامه های افزودنی ندارید! بیایید سعی کنیم:

CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

SELECT
  *
FROM
  firms
WHERE
  to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*')
ORDER BY
  lower(name) ~ ('^' || 'роза') DESC
, lower(name)
LIMIT 10;

[به توضیح.tensor.ru نگاه کنید]

در اینجا موازی سازی اجرای پرس و جو کمی به ما کمک کرد و زمان را به نصف کاهش داد 11 میلی‌ثانیه. و ما مجبور شدیم 1.5 برابر کمتر بخوانیم - در کل 20MB. اما در اینجا، هرچه کمتر، بهتر است، زیرا هر چه حجم بیشتری را می خوانیم، شانس بیشتری برای از دست دادن حافظه پنهان وجود دارد، و هر صفحه اضافی از اطلاعات خوانده شده از دیسک یک "ترمز" بالقوه برای درخواست است.

1.3: هنوز هم دوست دارم؟

خواسته قبلی برای همه خوبه ولی روزی صد هزار بار بکشی میاد 2TB خواندن داده ها در بهترین حالت، از حافظه، اما اگر بدشانس هستید، از دیسک. پس بیایید سعی کنیم آن را کوچکتر کنیم.

بیایید به یاد بیاوریم که کاربر چه چیزی را می خواهد ببیند اول "که با ... شروع می شود". بنابراین این در خالص ترین شکل خود است جستجوی پیشوند با کمک text_pattern_ops! و فقط اگر تا 10 رکورد مورد نظر "به اندازه کافی نداشته باشیم"، باید خواندن آنها را با استفاده از جستجوی FTS به پایان برسانیم:

CREATE INDEX ON firms(lower(name) text_pattern_ops);

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
LIMIT 10;

[به توضیح.tensor.ru نگاه کنید]

عملکرد عالی - کل 0.05 میلی‌ثانیه و کمی بیشتر از 100 کیلوبایت خواندن! فقط ما فراموش کردیم به ترتیب نامتا کاربر در نتایج گم نشود:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name)
LIMIT 10;

[به توضیح.tensor.ru نگاه کنید]

اوه، چیزی دیگر آنقدر زیبا نیست - به نظر می رسد یک شاخص وجود دارد، اما مرتب سازی از آن عبور می کند ... البته، قبلاً چندین برابر بیشتر از گزینه قبلی مؤثر است، اما ...

1.4: "پایان با یک فایل"

اما شاخصی وجود دارد که به شما امکان می دهد بر اساس محدوده جستجو کنید و همچنان از مرتب سازی به طور معمول استفاده کنید - btree منظم!

CREATE INDEX ON firms(lower(name));

فقط درخواست برای آن باید "به صورت دستی جمع آوری شود":

SELECT
  *
FROM
  firms
WHERE
  lower(name) >= 'роза' AND
  lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
ORDER BY
   lower(name)
LIMIT 10;

[به توضیح.tensor.ru نگاه کنید]

عالی - مرتب سازی کار می کند و مصرف منابع "میکروسکوپی" باقی می ماند. هزاران بار موثرتر از FTS "خالص".! تنها چیزی که باقی می ماند این است که آن را در یک درخواست واحد قرار دهیم:

(
  SELECT
    *
  FROM
    firms
  WHERE
    lower(name) >= 'роза' AND
    lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
  ORDER BY
     lower(name)
  LIMIT 10
)
UNION ALL
(
  SELECT
    *
  FROM
    firms
  WHERE
    to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
    lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
  ORDER BY
    lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
  , lower(name)
  LIMIT 10
)
LIMIT 10;

توجه داشته باشید که پرس و جو دوم اجرا می شود فقط در صورتی که اولین مورد کمتر از حد انتظار بازگشت داشته باشد آخرین LIMIT تعداد خطوط من در مورد این روش بهینه سازی پرس و جو صحبت می کنم قبلا نوشته بود.

بنابراین بله، ما اکنون هم btree و هم gin را روی میز داریم، اما از نظر آماری معلوم می شود که کمتر از 10 درصد درخواست ها به اجرای بلوک دوم می رسد. یعنی با چنین محدودیت‌های معمولی که از قبل برای کار شناخته شده‌اند، توانستیم کل مصرف منابع سرور را تقریباً هزار برابر کاهش دهیم!

1.5*: می توانیم بدون فایل کار کنیم

بالاتر LIKE ما از استفاده از مرتب سازی نادرست جلوگیری شدیم. اما می توان آن را با مشخص کردن عملگر USING "در مسیر درست قرار داد":

به طور پیش فرض فرض می شود ASC. علاوه بر این، می توانید نام یک عملگر مرتب سازی خاص را در یک بند مشخص کنید USING. عملگر مرتب‌سازی باید عضوی از کمتر یا بیشتر از برخی از خانواده‌های عملگرهای درختی B باشد. ASC معمولا معادل USING < и DESC معمولا معادل USING >.

در مورد ما، "کمتر" است ~<~:

SELECT
  *
FROM
  firms
WHERE
  lower(name) LIKE ('роза' || '%')
ORDER BY
  lower(name) USING ~<~
LIMIT 10;

[به توضیح.tensor.ru نگاه کنید]

2: چگونه درخواست ها ترش می شوند

اکنون ما درخواست خود را به مدت شش ماه یا یک سال به "جوش کشیدن" می گذاریم و از اینکه دوباره آن را "در بالای" با شاخص های کل "پمپاژ" روزانه حافظه می یابیم شگفت زده می شویم (بافر به اشتراک گذاشته شده است) در 5.5TB - یعنی حتی بیشتر از آنچه در ابتدا بود.

نه، البته کسب و کار ما رشد کرده و حجم کار ما زیاد شده است، اما نه به همین میزان! این به این معنی است که چیزی در اینجا ماهیگیر است - بیایید آن را بفهمیم.

2.1: تولد صفحه بندی

در نقطه‌ای، تیم توسعه‌دهنده دیگری می‌خواست با نتایج مشابه، اما گسترده، امکان «پرش» از جستجوی سریع اشتراک به رجیستری را فراهم کند. رجیستری بدون پیمایش صفحه چیست؟ بیایید آن را خراب کنیم!

( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;

اکنون امکان نمایش رجیستری نتایج جستجو با بارگیری "صفحه به صفحه" بدون هیچ استرسی برای توسعه دهنده وجود داشت.

البته در واقع، برای هر صفحه بعدی از داده ها بیشتر و بیشتر خوانده می شود (همه مربوط به زمان قبلی است که ما آنها را کنار می گذاریم، به علاوه "دم" ضروری) - یعنی این یک ضد الگوی واضح است. اما درست تر است که جستجو را در تکرار بعدی از کلید ذخیره شده در رابط شروع کنیم، اما در مورد آن زمان دیگری.

2.2: من چیزی عجیب و غریب می خواهم

در مرحله ای توسعه دهنده می خواست نمونه به دست آمده را با داده ها متنوع کنید از جدول دیگری که کل درخواست قبلی به CTE ارسال شده است:

WITH q AS (
  ...
  LIMIT <N> + 10
)
SELECT
  *
, (SELECT ...) sub_query -- какой-то запрос к связанной таблице
FROM
  q
LIMIT 10 OFFSET <N>;

و با این حال، بد نیست، زیرا درخواست فرعی فقط برای 10 رکورد برگشتی ارزیابی می شود، اگر نه ...

2.3: DISTINCT بی معنی و بی رحم است

جایی در روند چنین تکاملی از پرس و جوی دوم گمشده NOT LIKE شرط. مشخص است که پس از این UNION ALL شروع به بازگشت کرد برخی از ورودی ها دو بار - ابتدا در ابتدای خط و سپس دوباره - در ابتدای کلمه اول این خط یافت می شود. در حد، تمام رکوردهای پرس و جوی دوم می توانند با رکوردهای اول مطابقت داشته باشند.

یک توسعه دهنده به جای جستجوی علت چه می کند؟.. سوالی نیست!

• دو برابر اندازه نمونه های اصلی
• DISTINCT را اعمال کنیدبرای به دست آوردن تنها نمونه های تکی از هر خط

WITH q AS (
  ( ... LIMIT <2 * N> + 10)
  UNION ALL
  ( ... LIMIT <2 * N> + 10)
  LIMIT <2 * N> + 10
)
SELECT DISTINCT
  *
, (SELECT ...) sub_query
FROM
  q
LIMIT 10 OFFSET <N>;

یعنی واضح است که نتیجه در نهایت دقیقاً یکسان است ، اما شانس "پرواز" به پرس و جوی دوم CTE بسیار بیشتر شده است و حتی بدون این ، به وضوح قابل خواندن تر است.

اما این غم انگیزترین چیز نیست. از آنجایی که توسعه دهنده درخواست انتخاب کرد DISTINCT نه برای موارد خاص، بلکه برای همه زمینه ها به طور همزمان رکوردها، سپس قسمت sub_query - نتیجه پرس و جوی فرعی - به طور خودکار در آنجا گنجانده شد. حالا برای اجرا DISTINCT، پایگاه داده باید قبلاً اجرا می شد نه 10 پرسش فرعی، بلکه همه <2 * N> + 10!

2.4: همکاری بیش از همه!

بنابراین، توسعه دهندگان ادامه دادند - آنها زحمتی نکشیدند، زیرا کاربر به وضوح حوصله کافی برای "تنظیم" رجیستری به مقادیر قابل توجه N با کندی مزمن در دریافت هر "صفحه" بعدی نداشت.

تا اینکه توسعه دهندگان بخش دیگری به سراغ آنها آمدند و خواستند از چنین روش مناسبی استفاده کنند برای جستجوی تکراری - یعنی یک قطعه را از مقداری نمونه می گیریم، آن را با شرایط اضافی فیلتر می کنیم، نتیجه را می کشیم، سپس قطعه بعدی را (که در مورد ما با افزایش N حاصل می شود) و به همین ترتیب تا زمانی که صفحه را پر کنیم.

به طور کلی، در نمونه صید شده N به مقادیر تقریباً 17K رسید، و تنها در یک روز حداقل 4K از این درخواست ها "در امتداد زنجیره" اجرا شد. آخرین آنها جسورانه توسط اسکن شدند 1 گیگابایت حافظه در هر تکرار...

در کل

منبع: www.habr.com