Skip to content

Instantly share code, notes, and snippets.

@radimih
Created April 4, 2017 04:35
Show Gist options
  • Save radimih/548656510805db7cba96770646c30d77 to your computer and use it in GitHub Desktop.
Save radimih/548656510805db7cba96770646c30d77 to your computer and use it in GitHub Desktop.
MySQL: функция бинарного поиска
DROP FUNCTION IF EXISTS squid_log.id_by_date;
CREATE FUNCTION `id_by_date`(day DATE)
RETURNS int(11)
DETERMINISTIC /* Чтобы в where-выражении функция не вызывалась для каждой записи */
READS SQL DATA
COMMENT 'Получить id записи, ближайшей к указанной дате'
BEGIN
/*******************************************************************************
* Получить id записи, ближайшей к указанной дате
* ----------------------------------------------
* Так как поле даты-времени не проиндексировано, используется бинарный поиск
* идентификатора записи по значению неиндексированного поля, значение которого
* также растет вместе с идентификатором записи.
*
* В данном случае таким полем выступает time_since_epoch - время создания
* записи в виде числа unixtime.
*
* Параметры:
* day - дата, на которую необходимо получить первый за сутки id
* FULL_SCAN_ROWS - количество записей, при котором поиск переходит с
* бинарного на последовательный
*
* Возврат:
* id - идентификатор первой записи на дату day или позже
* max id - если дата day превышает максимальную дату в таблице
* min id - если нет записей ранее day
* NULL - если таблица пустая
*******************************************************************************/
/*------------------------------------------------------------------------------
* Неиндексируемое поле: epoch_in_middle unix_day
* ......|--------------------|=============-*-====|
* Поле id: id_beg id_mid id_end
*-----------------------------------------------------------------------------*/
declare FULL_SCAN_ROWS int default 1000;
declare unix_day decimal(15, 3) default unix_timestamp(day);
declare epoch_in_middle decimal(15, 3);
declare id_beg int default 0;
declare id_end int default 0;
declare id_mid int default 0;
declare result int default null;
select min(id), max(id) into id_beg, id_end
from access_log;
# Проверить на граничные условия
# -- если таблица пустая
if id_end is null
then return null; end if;
# -- если дата unix_day меньше даты записи с минимальным id
if unix_day < (select time_since_epoch from access_log where id = id_beg) /* min */
then return id_beg; end if;
# -- если дата unix_day больше или равна дате записи с максимальным id
if unix_day >= (select time_since_epoch from access_log where id = id_end) /* max */
then return id_end; end if;
# Цикл бинарного поиска
while (id_end - id_beg) div 2 > FULL_SCAN_ROWS
do
set id_mid = id_beg + (id_end - id_beg) div 2;
select time_since_epoch into epoch_in_middle
from access_log
where id = id_mid;
# Если искомое значение (unix_day) находится в правой части отрезка
if unix_day >= epoch_in_middle
then
set id_beg = id_mid;
# Если искомое значение (unix_day) находится в левой части отрезка
else
set id_end = id_mid;
end if;
end while;
# Переход на последовательный поиск
select id into result
from access_log
where id between id_beg and id_end
and time_since_epoch >= unix_day
limit 1;
return result;
END;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment