SQL-запрос, который ищет строки, удовлетворяющие столбцу 1 <= X <= Column2, очень медленный

Ответ 1

Я нашел решение, основанное на свойствах данных в таблице. Я предпочел бы иметь более общее решение, которое не зависит от текущих данных, но пока что лучшее, что у меня есть.

Проблема с исходным запросом:

SELECT P, Y, Z FROM SomeTable WHERE FirstX <= ? AND LastX >= ? LIMIT 10;

заключается в том, что выполнение может потребовать сканирования большого процента записей в индексе FirstX, LastX, P, когда первое условие FirstX <= ? выполняется большим процентом строк.

Что я сделал для уменьшения времени выполнения, заметим, что LastX-FirstX относительно невелик.

Я выполнил запрос:

SELECT MAX(LastX-FirstX) FROM SomeTable;

и получил 4200000.

Это означает, что FirstX >= LastX – 4200000 для всех строк в таблице.

Итак, чтобы удовлетворить LastX >= ?, мы должны также удовлетворить FirstX >= ? – 4200000.

Таким образом, мы можем добавить условие к запросу следующим образом:

SELECT P, Y, Z FROM SomeTable WHERE FirstX <= ? AND FirstX >= ? - 4200000 AND LastX >= ? LIMIT 10;

В примере, который я тестировал в вопросе, количество обработанных индексных записей было уменьшено с 2104820 до 18, а время работы сократилось с 0,563 секунды до 0,0003 секунды.

Я тестировал новый запрос с теми же значениями 120000 X. Результат был идентичен старому запросу. Время сменилось на 10 часов на 5,5 минут, что превышает в 100 раз быстрее.

Ответ 2

WHERE col1 < ... AND ... < col2 практически невозможно оптимизировать.

Любой полезный запрос будет включать "диапазон" на col1 или col2. Два диапазона (в двух разных столбцах) не могут использоваться в одном INDEX.

Поэтому любой индекс, который вы пытаетесь, имеет риск проверки большого количества таблицы: INDEX(col1, ...) будет сканировать с начала на col1 col1. Аналогично для col2 и сканирования до конца.

Чтобы добавить к вашим бедам, диапазоны перекрываются. Таким образом, вы не можете потянуть быстрый и добавить ORDER BY ... LIMIT 1, чтобы быстро остановиться. И если вы скажете LIMIT 10, но есть только 9, это не остановится до начала/конца таблицы.

Одна простая вещь, которую вы можете сделать (но это не сильно ускорит процесс) - это обменять PRIMARY KEY и UNIQUE. Это может помочь, потому что InnoDB "кластеризует" ПК с данными.

Если диапазоны не совпадают, я бы указал вам на http://mysql.rjweb.org/doc.php/ipranges.

Итак, что можно сделать??? Как "четные" и "маленькие" являются диапазонами? Если они разумно "хороши", тогда следующий код будет принят, но должен быть намного быстрее. (В вашем примере 100000 500000 довольно уродливый, как вы увидите через минуту.)

Определите ведра, например, пол (число/100). Затем постройте таблицу, которая сопоставляет ведра и диапазоны. Примеры:

FirstX  LastX  Bucket
123411  123488  1234
222222  222444  2222
222222  222444  2223
222222  222444  2224
222411  222477  2224

Обратите внимание, что некоторые диапазоны "принадлежат" нескольким ковшикам.

Затем поиск выполняется сначала в ведрах (ов) в запросе, а затем в деталях. В поисках X = 222433 можно найти две строки с ведром = 2224, а затем решить, что оба варианта в порядке. Но для X = 222466 две строки имеют ведро, но только одно соответствует firstX и lastX.

WHERE bucket = FLOOR(X/100)
  AND firstX <= X
  AND X <= lastX

с

INDEX(bucket, firstX)

Но... с 100000 500000, было бы 4001 строк, потому что этот диапазон находится в том, что многие "ведра".

План B (для решения широкого диапазона)

Разделите диапазоны на широкий и узкий. Широкие диапазоны с помощью простого сканирования таблицы, выполняйте узкие диапазоны с помощью метода моего ковша. UNION ALL результаты вместе. Надеемся, что "широкая" таблица будет намного меньше, чем "узкая" таблица.

Ответ 3

Вам нужно добавить еще один индекс в LastX.

Уникальный индекс FirstLastXPriority_Index (FirstX, LastX, P) представляет конкатенацию этих значений, поэтому он будет бесполезен с 'AND LastX > =?' часть вашего предложения WHERE.

Ответ 4

Кажется, что единственный способ быстро выполнить запрос - уменьшить количество выбранных и сравниваемых полей. Вот идея.

Мы можем объявить новое индексированное поле (например, UNSIGNED BIGINT) и сохранить в нем оба значения FistX и LastX, используя смещение для одного из полей.

Например:

FirstX     LastX      CombinedX
100000     500000     100000500000
150000     220000     150000220000
180000     190000     180000190000
550000     660000     550000660000   
70000      90000      070000090000 
75         85         000075000085

альтернативой является объявление поля как DECIMAL и сохранение в нем FirstX + LastX/MAX (LastX). Позже найдите значения, удовлетворяющие условиям, сравнивающим значения с одним полем CombinedX.

прилагаемая

И затем вы можете получить строки, проверяющие только одно поле: чем-то вроде где param1 = 160000

SELECT * FROM new_table 
WHERE
(CombinedX <= 160000*1000000) AND
(CombinedX % 1000000 >= 160000);

Здесь я предполагаю, что для всех FistX < LastX. Конечно, вы можете заранее рассчитать смещение param1 * и сохранить его в переменной, с которой будут выполняться дальнейшие сравнения. Конечно, вы можете рассматривать не десятичные смещения, а побитовые сдвиги. Были выбраны десятичные смещения, поскольку их легче читать человеком для показа в образце.

Ответ 5

Эран, я считаю, что решение, которое вы нашли, , является лучшим с точки зрения минимальных затрат. В процессе оптимизации принято учитывать свойства распределения данных в БД. Более того, в больших системах обычно невозможно достичь удовлетворительной производительности, если природа данных не принимается во внимание.

Однако это решение также имеет недостатки. И наименьшая необходимость в изменении параметра конфигурации при каждом изменении данных. Более важным может быть следующее. Предположим, что в один прекрасный день в таблице появится очень большой диапазон. Например, пусть его длина охватывает половину всех возможных значений. Я не знаю характера ваших данных, поэтому я не могу точно знать, может ли такой диапазон появиться или нет, так что это всего лишь предположение. С точки зрения результата, все в порядке. Это просто означает, что примерно каждый второй запрос вернет еще одну запись. Но даже один такой интервал полностью уничтожит вашу оптимизацию, потому что условие FirstX <=? AND FirstX> =? - [MAX (LastX-FirstX)] больше не будет эффективно отсекать достаточное количество записей.

Поэтому, если у вас нет уверенности в том, что когда-либо появятся слишком длинные диапазоны, я предлагаю вам сохранить ту же идею, но взять ее с другой стороны. Я предлагаю при загрузке новых данных в таблицу разбить все длинные диапазоны на меньшие с длиной, не превышающей определенного значения. Вы написали, что The important columns of this table are FirstX, LastX, Y, Z and P. Таким образом, вы можете выбрать некоторое число N и каждый раз при загрузке данных в таблицу, если найден диапазон с LastX-FirstX > N, чтобы заменить его несколькими строками:

FirstX; FirstX + N
FirstX + N; FirstX + 2N
...
FirstX + kN; LastX

и для каждой строки сохраняйте те же значения Y, Z и P.

Для данных, подготовленных таким образом, ваш запрос всегда будет таким же:

SELECT P, Y, Z FROM SomeTable WHERE FirstX <=? AND FirstX> =? - N AND LastX> =?

и всегда будет одинаково эффективным.

Теперь, как выбрать наилучшее значение для N? Я бы сделал несколько экспериментов с разными ценностями и посмотрел, что будет лучше. И возможно, что оптимальный будет меньше текущей максимальной длины интервала 4200000. Сначала это может удивить, потому что уменьшение N, несомненно, сопровождается ростом таблицы, чтобы она могла стать намного больше, чем 4,3 миллиона. Но на самом деле огромный размер таблицы не является проблемой, когда ваш запрос использует индекс достаточно хорошо. И в этом случае с уменьшением N индекс будет использоваться все более эффективно.

Ответ 6

Индексы не помогут вам в этом сценарии, за исключением небольшого процента всех возможных значений X.

Давайте скажем, например:

• FirstX содержит значения от 1 до 1000 равномерно распределенных
• LastX содержит значения от 1 до 1042 равномерно распределенных

И у вас есть следующие индексы:

• FirstX, LastX, <covering columns>
• LastX, FirstX, <covering columns>

Сейчас:

• Если X равно 50, то предложение FirstX <= 50 соответствует приблизительно 5% строк, а LastX >= 50 соответствует приблизительно 95% строк. MySQL будет использовать первый индекс.

• Если X равно 990, то предложение FirstX <= 990 соответствует приблизительно 99% строк, а LastX >= 990 соответствует приблизительно 5% строк. MySQL будет использовать второй индекс.

• Любой X между этими двумя приведет к тому, что MySQL не будет использовать ни один из индексов (я не знаю точного порога, но 5% работал в моих тестах). Даже если MySQL использует индекс, слишком много совпадений, и индекс, скорее всего, будет использоваться для покрытия вместо поиска.

Ваше решение - лучшее. Что вы делаете, это определение верхней и нижней границы поиска "диапазон":

WHERE FirstX <= 500      -- 500 is the middle (worst case) value
AND   FirstX >= 500 - 42 -- range matches approximately 4.3% rows
AND   ...

Теоретически это должно работать, даже если вы ищете FirstX для значений в середине. Сказав это, вам повезло с достоинством 4200000; возможно, потому что максимальная разница между первым и последним составляет меньший процент.

Если это поможет, вы можете сделать следующее после загрузки данных:

ALTER TABLE testdata ADD COLUMN delta INT NOT NULL;
UPDATE testdata SET delta = LastX - FirstX;
ALTER TABLE testdata ADD INDEX delta (delta);

Это облегчает выбор MAX(LastX - FirstX).

Я тестировал MySQL SPATIAL INDEXES, который можно было использовать в этом сценарии. К сожалению, я обнаружил, что пространственные индексы медленнее и имеют множество ограничений.

Ответ 7

Изменить: Идея № 2

У вас есть контроль над Java-приложением? Потому что, честно говоря, 0,3 секунды для сканирования индекса неплохо. Ваша проблема в том, что вы пытаетесь получить запрос, запустив 120 000 раз, чтобы иметь разумное время окончания.

Если у вас есть контроль над Java-приложением, вы можете либо сразу отправить все значения X, либо позволить SQL не выполнять сканирование индекса 120k раз. Или вы могли бы просто запрограммировать логику на стороне Java, так как было бы относительно легко оптимизировать.

Оригинальная идея:

Вы пытались создать индекс с несколькими столбцами?

Проблема с наличием нескольких индексов состоит в том, что каждый индекс будет только сузить его до ~ 50% от записей - он должен затем сопоставить эти ~ 2 миллиона строк индекса A с ~ 2 миллионами строк индекса B.

Вместо этого, если вы получите оба столбца в одном индексе, SQL-движок сначала может выполнить операцию поиска, чтобы перейти к началу записей, а затем выполнить одно индексное сканирование, чтобы получить список требуемых записей. Нет сопоставления одного индекса с другим.

Я бы предложил не делать это кластеризованным индексом. Причина этого? Вы не ожидаете много результатов, поэтому сопоставление результатов сканирования индекса с таблицей не займет много времени. Вместо этого вы хотите сделать индекс как можно меньшим, чтобы сканирование индекса выполнялось как можно быстрее. Кластеризованные индексы - это таблица, поэтому кластерный индекс будет иметь такую ​​же скорость сканирования, как и сама таблица. В то же время вы, вероятно, не хотите, чтобы в вашем индексе были другие поля, отличные от FirstX и LastX, - сделайте этот индекс настолько маленьким, насколько сможете, чтобы сканирование проходило.

Наконец, как и сейчас, вам нужно будет понять двигатель, потому что вы не ожидаете большого набора данных из поиска - вы хотите убедиться, что он использует этот компактный индекс для его сканирование (вместо того, чтобы говорить "Eh, мне было бы лучше просто выполнить полное сканирование таблицы.)

Ответ 8

Один из способов может состоять в том, чтобы разбить таблицу на разные диапазоны, а затем запросить материал, который вписывается в диапазон, следовательно, количество, необходимое для проверки намного меньше. Это может не сработать, так как java может быть медленнее. Но это может снизить нагрузку на базу данных. Возможно, также существует возможность не запрашивать базу данных столько раз и иметь более инклюзивный SQL (вы можете отправить список значений и отправить его в другую таблицу).

Ответ 9

Предположим, вы получили время выполнения до 0,1 секунды. Будет ли приемлемым 3 часа, двадцать минут?

Простым фактом является то, что тысячи вызовов одного и того же запроса невероятно неэффективны. В целом, помимо того, что должна выдержать база данных, есть сетевой трафик, который нужно учитывать, время поиска диска и всевозможные накладные расходы.

Предположим, что у вас еще нет 120 000 значений для x в таблице, где я бы начал. Я бы вставлял их в таблицу партиями по 500 или около того за раз:

insert into xvalues (x)
select 14 union all
select 18 union all
select 42 /* and so on */

Затем измените свой запрос, чтобы присоединиться к xvalues.

Я полагаю, что только оптимизация позволит вам сократить время выполнения до нескольких минут или секунд вместо часов (на основе многих таких оптимизаций, которые я сделал на протяжении многих лет).

Он также открывает дверь для дальнейших оптимизаций. Если значения x имеют, по крайней мере, несколько дубликатов (например, не менее 20% значений встречаются более одного раза), возможно, стоит изучить решение, в котором вы выполняете запрос только для уникальных значений и вставляете в SomeTable для каждого x с соответствующим значением.

Как правило: все, что вы можете делать в массе, скорее всего, будет экспоненциально превосходить все, что вы делаете по строкам.

PS:

Вы ссылались на запрос, но хранимая процедура также может работать с таблицей ввода. В некоторых РСУБД вы можете передать таблицу в качестве параметра. Я не думаю, что это работает в MySQL, но вы можете создать временную таблицу, заполняемую вызывающим кодом, и к ней присоединяется хранимая процедура. Или постоянная таблица используется одинаково. Основным недостатком использования временной таблицы является то, что вам может потребоваться заниматься управлением сеансом или отбрасывать устаревшие данные. Только вы узнаете, применимо ли это к вашему делу.

Ответ 10

Итак, у меня нет достаточного количества данных, чтобы быть уверенным в времени выполнения. Это будет работать, только если столбец P уникален? Чтобы получить два индекса, я создал два индекса и следующий запрос...

Index A - FirstX, P, Y, Z
Index B - P, LastX

Это запрос

select A.P, A.Y, A.Z 
from 
    (select P, Y, Z from asdf A where A.firstx <= 185000 ) A
    join 
    (select P from asdf A where A.LastX >= 185000 ) B
    ON A.P = B.P

По какой-то причине это показалось быстрее, чем

select A.P, A.Y, A.Z 
from asdf A join asdf B on A.P = B.P
where A.firstx <= 185000 and B.LastX >= 185000

Ответ 11

Чтобы оптимизировать этот запрос:

SELECT P, Y, Z FROM SomeTable WHERE FirstX < =? И LastX > =? LIMIT 10;

Здесь 2 ресурса, которые вы можете использовать:

• нисходящие индексы
• пространственные индексы

Убывающие индексы:

Один из вариантов - использовать индекс, который спускается по FirstX и восходит по LastX.

https://dev.mysql.com/doc/refman/8.0/en/descending-indexes.html

что-то вроде:

CREATE INDEX SomeIndex на SomeTable (FirstX DESC, LastX);

И наоборот, вы можете создать вместо этого индекс (LastX, FirstX DESC).

Пространственные индексы:

Другой вариант - использовать ПРОСТРАНСТВЕННЫЙ ИНДЕКС с (FirstX, LastX). Если вы считаете, что FirstX и LastX как 2D пространственные координаты, то ваш поиск, что он делает, - это выбрать точки в смежной географической области, ограниченные линиями FirstX <= LastX, FirstX >= 0, LastX >= X.

Здесь ссылка на пространственные индексы (не относящиеся к MySQL, но с рисунками):

https://docs.microsoft.com/en-us/sql/relational-databases/spatial/spatial-indexes-overview

Ответ 12

Другой подход заключается в предварительном расчете решений, если это число не слишком велико.

CREATE TABLE SomeTableLookUp (
    X INT NOT NULL
    PrimaryKeyCol BIGINT NOT NULL,
    PRIMARY KEY(X, PrimaryKeyCol)
);

А теперь вы просто предварительно заполнили свою постоянную таблицу.

INSERT INTO SomeTableLookUp
SELECT X, PrimaryKeyCol
FROM SomeTable
JOIN (
   SELECT DISTINCT X FROM SomeTable 
) XS
WHERE XS.X BETWEEN StartX AND EndX 

И теперь вы можете выбрать свои ответы напрямую.

SELECT SomeTable.*
FROM SomeTableLookup
JOIN SomeTable
ON SomeTableLookup.PrimaryKeyCol = SomeTable.PrimaryKeyCol
WHERE SomeTableLookup = ?
LIMIT 10