MySQL: функция бинарного поиска

id_by_date.sql

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;