Thread: Поиск ближайшего

Поиск ближайшего

From

"Evgeny M. Baldin"

Date:

06 April 2005, 15:57:02

Добрый день

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

 Преамбула: ключом является время BeginTime. Запросу тоже передаётся
время Time. По запросу необходимо выдернуть ближайшую по времени запись,
где BeginTime<=Time (назовём эту запись валидной для Time)

 Амбула: Запрос представляет из себя фразу типа:

select * from таблица where BeginTime<=Time
                       order by BeginTime desc limit 1;

Индексы работают, одиночные запросы проходят более-менее быстро, хотя тоже
хотелось бы побыстрее.

А вот попытка сопоставить валидные записи для массива времён, особенно
когда число записей в таблице превышает десятки тысяч наступает полный :(

Что хотелось бы: когда идёт поиск для какого-то числа на предмет
равенства, то используется бинарный поиск - это быстро. Хотелось бы иметь
поиск подобного рода, но не на предмет поиска точного значения, а на
предмет поиска ближайшего. Как я понимаю по числу действий это тоже самое,
просто надо помнить предыдущее число.

То есть нужен оператор типа равенства - назовём его CLOSE TO для работы с
временными данными, стой же самой скоростью работы для быстрого
сопоставления.

С уважением
    Евгений

P.S.  Я не программист - я пользователь, поэтому хотелось бы получить
результат малой кровью.

Re: Поиск ближ

From

Teodor Sigaev

Date:

06 April 2005, 16:50:38


Evgeny M. Baldin wrote:
> Добрый день
>
>  Так уж случилось, что на эксперименте для целей медленного контроля и
> калибровок стали использовать PostgreSQL. К сожалению средство оказалось
> не совсем адекватным для нужным нам целей.
>
>  Преамбула: ключом является время BeginTime. Запросу тоже передаётся
> время Time. По запросу необходимо выдернуть ближайшую по времени запись,
> где BeginTime<=Time (назовём эту запись валидной для Time)
>
>  Амбула: Запрос представляет из себя фразу типа:
>
> select * from таблица where BeginTime<=Time
>                        order by BeginTime desc limit 1;
>
> Индексы работают, одиночные запросы проходят более-менее быстро, хотя тоже
> хотелось бы побыстрее.
>
> А вот попытка сопоставить валидные записи для массива времён, особенно
> когда число записей в таблице превышает десятки тысяч наступает полный :(

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


>
> Что хотелось бы: когда идёт поиск для какого-то числа на предмет
> равенства, то используется бинарный поиск - это быстро. Хотелось бы иметь
> поиск подобного рода, но не на предмет поиска точного значения, а на
> предмет поиска ближайшего. Как я понимаю по числу действий это тоже самое,
> просто надо помнить предыдущее число.

Поиск первого занчения по условию < или > ничем не отличается от поиска на
равенство, поскольку алгоритм тот же.



>
> То есть нужен оператор типа равенства - назовём его CLOSE TO для работы с
> временными данными, стой же самой скоростью работы для быстрого
> сопоставления.
>
> С уважением
>     Евгений
>
> P.S.  Я не программист - я пользователь, поэтому хотелось бы получить
> результат малой кровью.
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
>       subscribe-nomail command to majordomo@postgresql.org so that your
>       message can get through to the mailing list cleanly

--
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/

Re: Поиск ближайшего

From

Oleg Bartunov

Date:

06 April 2005, 17:34:43

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

---559023410-824023566-1112783683=:9870
Content-Type: TEXT/PLAIN; charset=koi8-r; format=flowed
Content-Transfer-Encoding: 8BIT

Евгений,

так дело не пойдет и никто вам не поможет. Несмотря на то, что вы описали
постановку задачи, вы совсем ничего не сказали о системе, постгресе,
а последний запрос ввобще проигнорировали. Нужно сообщать как минимум:

1. Система
2. версия постгреса
3. структура таблицы (\d tablename)
4. запрос + explain analyze

Думаю, что это доступно и не программисту и уж совсем не требует крови.

Олег


On Wed, 6 Apr 2005, Evgeny M. Baldin wrote:

> Добрый день
>
> Так уж случилось, что на эксперименте для целей медленного контроля и
> калибровок стали использовать PostgreSQL. К сожалению средство оказалось
> не совсем адекватным для нужным нам целей.
>
> Преамбула: ключом является время BeginTime. Запросу тоже передаётся
> время Time. По запросу необходимо выдернуть ближайшую по времени запись,
> где BeginTime<=Time (назовём эту запись валидной для Time)
>
> Амбула: Запрос представляет из себя фразу типа:
>
> select * from таблица where BeginTime<=Time
>                       order by BeginTime desc limit 1;
>
> Индексы работают, одиночные запросы проходят более-менее быстро, хотя тоже
> хотелось бы побыстрее.
>
> А вот попытка сопоставить валидные записи для массива времён, особенно
> когда число записей в таблице превышает десятки тысяч наступает полный :(
>
> Что хотелось бы: когда идёт поиск для какого-то числа на предмет
> равенства, то используется бинарный поиск - это быстро. Хотелось бы иметь
> поиск подобного рода, но не на предмет поиска точного значения, а на
> предмет поиска ближайшего. Как я понимаю по числу действий это тоже самое,
> просто надо помнить предыдущее число.
>
> То есть нужен оператор типа равенства - назовём его CLOSE TO для работы с
> временными данными, стой же самой скоростью работы для быстрого
> сопоставления.
>
> С уважением
>     Евгений
>
> P.S.  Я не программист - я пользователь, поэтому хотелось бы получить
> результат малой кровью.
>
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
>      subscribe-nomail command to majordomo@postgresql.org so that your
>      message can get through to the mailing list cleanly
>

     Regards,
         Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83
---559023410-824023566-1112783683=:9870--

Re: Поиск ближайшего

From

"Evgeny M. Baldin"

Date:

06 April 2005, 19:34:20

Добрый день

On Wed, 6 Apr 2005, Oleg Bartunov wrote:

> 1. Система
~$cat /etc/redhat-release
Red Hat Linux release 6.2 (Zoot)

~$cat /proc/cpuinfo
model name      : Pentium II (Klamath)
cpu MHz         : 300.686
bogomips        : 599.65

Планируется в ближайший месяц апгрейд на двухпроцессорный
AMD Opteron(tm) 240. Сейчас думаю имеет ли смысл связываться с PostgreSQL
8.0 или подождать до 8.3

> 2. версия постгреса

7.3.4 (Возможно переход на 8.0)

> 3. структура таблицы (\d tablename)

 Например (одна из двухсот схожих таблиц)
 \d vepp4current_key

                                      Таблица "public.vepp4current_key"
  Колонка   |           Тип            |         Модификаторы
------------+--------------------------+---------------------------------------------------------------------
 inserttime | timestamp with time zone |
 begintime  | timestamp with time zone | not null
 endtime    | timestamp with time zone |
 ver        | integer                  | not null
 rowid      | integer                  | not null default nextval('public.vepp4current_key_rowid_seq'::text)

Индексы: vepp4current_key_time_ver_key ключевое поле btree (begintime, ver),
         vepp4current_key_rowid_key unique btree (rowid)

> 4. запрос + explain analyze

Если я ищу ближайшую валидную запись:

calibrations=# EXPLAIN ANALYZE select begintime from vepp4current_key
where begintime<'yesterday' order by begintime limit 1;

QUERY PLAN

-------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.04 rows=1 width=8) (actual time=43.70..43.74 rows=1
loops=1)
   ->  Index Scan using vepp4current_key_time_ver_key on vepp4current_key
(cost=0.00..3329.39 rows=82047 width=8) (actual time=43.69..43.72 rows=2
loops=1)
         Index Cond: (begintime < '2005-04-05 00:00:00+07'::timestamp with
time zone)
 Total runtime: 43.94 msec
                ----------
(записей: 4)

 Если я ищу по строгому равенству

calibrations=# EXPLAIN ANALYZE select begintime from vepp4current_key
where begintime='yesterday' order by begintime limit 1;
                                                                     QUERY
PLAN

----------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..5.26 rows=1 width=8) (actual time=1.14..1.14 rows=0
loops=1)
   ->  Index Scan using vepp4current_key_time_ver_key on vepp4current_key
(cost=0.00..5.26 rows=1 width=8) (actual time=1.13..1.13 rows=0 loops=1)
         Index Cond: (begintime = '2005-04-05 00:00:00+07'::timestamp with
time zone)
 Total runtime: 1.34 msec
                ---------
(записей: 4)


Видно, что отличие в 30 раз (50 мс против 1.3 мс) - хотелось бы это как-то
ликвидировать. Странно, что ничего подобного мне обнаружить не удалось -
вроде поиск по времени вполне распространённая задача.

С уважением
    Евгений


> Думаю, что это доступно и не программисту и уж совсем не требует крови.

P.S. Я только сегодня подписался на список рассылки и не знал об имеющихся
правилах. Текст моего первого сообщения ниже.

>
> On Wed, 6 Apr 2005, Evgeny M. Baldin wrote:
>
> > Добрый день
> >
> > Так уж случилось, что на эксперименте для целей медленного контроля и
> > калибровок стали использовать PostgreSQL. К сожалению средство оказалось
> > не совсем адекватным для нужным нам целей.
> >
> > Преамбула: ключом является время BeginTime. Запросу тоже передаётся
> > время Time. По запросу необходимо выдернуть ближайшую по времени запись,
> > где BeginTime<=Time (назовём эту запись валидной для Time)
> >
> > Амбула: Запрос представляет из себя фразу типа:
> >
> > select * from таблица where BeginTime<=Time
> >                       order by BeginTime desc limit 1;
> >
> > Индексы работают, одиночные запросы проходят более-менее быстро, хотя тоже
> > хотелось бы побыстрее.
> >
> > А вот попытка сопоставить валидные записи для массива времён, особенно
> > когда число записей в таблице превышает десятки тысяч наступает полный :(
> >
> > Что хотелось бы: когда идёт поиск для какого-то числа на предмет
> > равенства, то используется бинарный поиск - это быстро. Хотелось бы иметь
> > поиск подобного рода, но не на предмет поиска точного значения, а на
> > предмет поиска ближайшего. Как я понимаю по числу действий это тоже самое,
> > просто надо помнить предыдущее число.
> >
> > То есть нужен оператор типа равенства - назовём его CLOSE TO для работы с
> > временными данными, стой же самой скоростью работы для быстрого
> > сопоставления.
> >
> > С уважением
> >     Евгений
> >
> > P.S.  Я не программист - я пользователь, поэтому хотелось бы получить
> > результат малой кровью.

Re: Поиск ближайшего

From

Oleg Bartunov

Date:

06 April 2005, 19:52:21

This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

---559023410-1423418003-1112791941=:9870
Content-Type: TEXT/PLAIN; charset=koi8-r; format=flowed
Content-Transfer-Encoding: 8BIT

On Wed, 6 Apr 2005, Evgeny M. Baldin wrote:

> AMD Opteron(tm) 240. Сейчас думаю имеет ли смысл связываться с PostgreSQL
> 8.0 или подождать до 8.3

Ох и долго ждать будешь :) Сейчас выйдет 8.02, beta уже доступна

>
>> 2. версия постгреса
>
> 7.3.4 (Возможно переход на 8.0)
>
>> 3. структура таблицы (\d tablename)
>
> Например (одна из двухсот схожих таблиц)
> \d vepp4current_key
>
>                                      Таблица "public.vepp4current_key"
>  Колонка   |           Тип            |         Модификаторы
> ------------+--------------------------+---------------------------------------------------------------------
> inserttime | timestamp with time zone |
> begintime  | timestamp with time zone | not null
> endtime    | timestamp with time zone |
> ver        | integer                  | not null
> rowid      | integer                  | not null default nextval('public.vepp4current_key_rowid_seq'::text)
>
> Индексы: vepp4current_key_time_ver_key ключевое поле btree (begintime, ver),
>         vepp4current_key_rowid_key unique btree (rowid)
>
>> 4. запрос + explain analyze
>
> Если я ищу ближайшую валидную запись:
>
> calibrations=# EXPLAIN ANALYZE select begintime from vepp4current_key
> where begintime<'yesterday' order by begintime limit 1;
>
> QUERY PLAN
>
-------------------------------------------------------------------------------------------------------------------------------------------------------------
> Limit  (cost=0.00..0.04 rows=1 width=8) (actual time=43.70..43.74 rows=1
> loops=1)
>   ->  Index Scan using vepp4current_key_time_ver_key on vepp4current_key
> (cost=0.00..3329.39 rows=82047 width=8) (actual time=43.69..43.72 rows=2
> loops=1)
>         Index Cond: (begintime < '2005-04-05 00:00:00+07'::timestamp with
> time zone)
> Total runtime: 43.94 msec
>                ----------
> (записей: 4)
>

а ты vacuum analyze давно делал ? Похоже, что здесь у тебя проблемы.
rows=82047 - это то, что планнер оценивает исходя из pg_stats,
а получает реально - rows=2 ! Ну куда это годится :)
Либо у тебя распределение сильно неправильное, что обычная гисторграмма на
10 бинов недостаточна (тогда надо увеличивать количесвто), либо элементарно
не делал vacuum analyze;
>
>
> Видно, что отличие в 30 раз (50 мс против 1.3 мс) - хотелось бы это как-то
> ликвидировать. Странно, что ничего подобного мне обнаружить не удалось -
> вроде поиск по времени вполне распространённая задача.

Если интересно, какие ключевые слова вы использовали и где ?

как  совет на будущее, использовать явный cast

  'yesterday'::timestamp with time zone;

планнер, конечно, все понял, но иногда могут быть проблемы


>

     Regards,
         Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83
---559023410-1423418003-1112791941=:9870--

Re: Поиск ближайшего

From

Oleg Bartunov

Date:

06 April 2005, 20:06:07

  This message is in MIME format.  The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware tools.

---559023410-1691952160-1112792767=:9870
Content-Type: TEXT/PLAIN; charset=koi8-r; format=flowed
Content-Transfer-Encoding: 8BIT

On Wed, 6 Apr 2005, Oleg Bartunov wrote:

> On Wed, 6 Apr 2005, Evgeny M. Baldin wrote:
>
>>
>> calibrations=# EXPLAIN ANALYZE select begintime from vepp4current_key
>> where begintime<'yesterday' order by begintime limit 1;
>>

кстати, а сколько всего записей без ' limit 1' ?
Если там много, то чудес нет, сортировать десятки тысяч записей требуется
время. Поэтому тебе надо использовать range, т.е. задать разумный
нижний предел и не париться. Это дело приложения и серого вещества
разработчиков приложения.

Другое дело, и мы пару раз этот вопрос поднимали, что limit на самом деле
является синтаксической затычкой, т.е. все вытаскивается, сортируется
согласно order by, а потом тупо и грязно вытаскиваются необходимые данные.
На самом деле, все можно делать по уму, т.е. использовать partial sort,
например, в твоей задаче надо вытащить только 1 строчку, а про все остальные
тебе совсем не важно, поэтому и сортировку можно остановить.
Есть и еще алгоритмы.  А ключевым словом, к твоей задаче является
'top-k query' и на этк тему написаноо куча работ. Мы с Федей Сигаевым
года три назад даже патч сделали, но тогда его не приняли из-за его
плохой реализации.

>

     Regards,
         Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83
---559023410-1691952160-1112792767=:9870--

Re: Поиск ближ

From

Teodor Sigaev

Date:

06 April 2005, 20:26:12


Oleg Bartunov wrote:
> On Wed, 6 Apr 2005, Oleg Bartunov wrote:
>
>> On Wed, 6 Apr 2005, Evgeny M. Baldin wrote:
>>
>>>
>>> calibrations=# EXPLAIN ANALYZE select begintime from vepp4current_key
>>> where begintime<'yesterday' order by begintime limit 1;
>>>
>
> кстати, а сколько всего записей без ' limit 1' ?
> Если там много, то чудес нет, сортировать десятки тысяч записей требуется
> время. Поэтому тебе надо использовать range, т.е. задать разумный нижний
> предел и не париться. Это дело приложения и серого вещества
> разработчиков приложения.
>
Постгрес умнее, в данном случае он не сортирует, он пользуетсся свойством
индекса: при линейной выборке из индекса данные уже сортированы.



>
> Другое дело, и мы пару раз этот вопрос поднимали, что limit на самом деле
> является синтаксической затычкой, т.е. все вытаскивается, сортируется
> согласно order by, а потом тупо и грязно вытаскиваются необходимые данные.
> На самом деле, все можно делать по уму, т.е. использовать partial sort,
> например, в твоей задаче надо вытащить только 1 строчку, а про все
> остальные
> тебе совсем не важно, поэтому и сортировку можно остановить.
> Есть и еще алгоритмы.  А ключевым словом, к твоей задаче является
> 'top-k query' и на этк тему написаноо куча работ. Мы с Федей Сигаевым
> года три назад даже патч сделали, но тогда его не приняли из-за его
> плохой реализации.
>
>
>
>
>>
>
>     Regards,
>         Oleg
> _____________________________________________________________
> Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
> Sternberg Astronomical Institute, Moscow University (Russia)
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(095)939-16-83, +007(095)939-23-83
> ---------------------------(end of broadcast)---------------------------
> TIP 3: if posting/reading through Usenet, please send an appropriate
>      subscribe-nomail command to majordomo@postgresql.org so that your
>      message can get through to the mailing list cleanly

--
Teodor Sigaev                                   E-mail: teodor@sigaev.ru
                                                    WWW: http://www.sigaev.ru/

Re: Поиск ближайшего

From

"Evgeny M. Baldin"

Date:

06 April 2005, 20:44:31

Добрый день

On Wed, 6 Apr 2005, Oleg Bartunov wrote:

> а ты vacuum analyze давно делал ? Похоже, что здесь у тебя проблемы.
> rows=82047 - это то, что планнер оценивает исходя из pg_stats,
> а получает реально - rows=2 ! Ну куда это годится :)
> Либо у тебя распределение сильно неправильное, что обычная гисторграмма на
> 10 бинов недостаточна (тогда надо увеличивать количесвто), либо элементарно
> не делал vacuum analyze;

Что за гистограммы и что надо с ними делать?

vacuum analyze делается раз в сутки вместе с бэкапом

строчка в crontab:

00 3 * * * vacuumdb -a -z  ; /volume/3/var_lib_pgsql/bin/dumpdb.pl

Делать vacuum analyze чаще чем раз в сутки не реально - машина слабая, а
база используется довольно активно. Не сменили её по причине
исключительной стабильности конкретной машины (последняя пара попыток
закончилась крахом - так что теперь на воду дуем).

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

А, кажется нашёл: тест на равенство я делал сразу после неравенства, то
есть данные уже были в кэше, ежели обратиться к той таблице, к которой не
обращался, то вообще ужас получается

calibrations=# EXPLAIN ANALYZE select begintime from kelktemp_key where
begintime='yesterday' order by begintime limit 1;
                                                                   QUERY
PLAN

------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..5.80 rows=1 width=8) (actual time=525.04..525.04
rows=0 loops=1)
   ->  Index Scan using kelktemp_key_time_ver_key on kelktemp_key
(cost=0.00..5.80 rows=1 width=8) (actual time=525.02..525.02 rows=0
loops=1)
         Index Cond: (begintime = '2005-04-05 00:00:00+07'::timestamp with
time zone)
 Total runtime: 525.30 msec
                -----
(записей: 4)

> > Видно, что отличие в 30 раз (50 мс против 1.3 мс) - хотелось бы это как-то
> > ликвидировать. Странно, что ничего подобного мне обнаружить не удалось -
> > вроде поиск по времени вполне распространённая задача.
>
> Если интересно, какие ключевые слова вы использовали и где ?

по сайту PostgreSQL, слова сейчас даже и не вспомню - что-то вроде time
interval. Изначально идея была основываться на временных интервалах - то
есть каждая запись имеет BeginTime и EndTime - но проблемы с поиском
перекрытий, а так же отсутствие реальной необходимости трансформировали
всё к ключу по одному времени.

> как совет на будущее, использовать явный cast
>
>   'yesterday'::timestamp with time zone;
>
> планнер, конечно, все понял, но иногда могут быть проблемы

В программе так и делаю, а прилагаемый select был просто набран для
примера, поэтому явного каста писать не стал. Кстати, замечено, что если
указать просто timestamp без timezone, то наступают вилы - видимо, это
чем-то объясняется, хотя странно - и там и сям время.

С уважением
    Евгений

P.S. Странно, что max и min сканируют всю таблицу как любые агрегатные
функции - причина понятна, но конкретно эти функции можно было вполне
сделать и поинтеллектуальнее. Я так понял, что не я один на эти грабли
наступил.

P.P.S. На сколько 8 с копейками стабильно по сравнению с 7.3.4 например
для тех же задач?

Re: Поиск ближайшего

From

"Evgeny M. Baldin"

Date:

06 April 2005, 20:49:13

Добрый день

On Wed, 6 Apr 2005, Oleg Bartunov wrote:

> кстати, а сколько всего записей без ' limit 1' ?
> Если там много, то чудес нет, сортировать десятки тысяч записей требуется
> время. Поэтому тебе надо использовать range, т.е. задать разумный
> нижний предел и не париться. Это дело приложения и серого вещества
> разработчиков приложения.

У нас данные эксперимента за несколько лет (пока три года - будет больше)
и их все может потребоваться обработать с учёт данных калибровок и
медленного контроля. А число записей очень по разному - от штук, до
десятков тысяч. Модифицировать поведение для каждой таблицы не получится
- слишком их много, меня одного мало :).

> Другое дело, и мы пару раз этот вопрос поднимали, что limit на самом деле
> является синтаксической затычкой, т.е. все вытаскивается, сортируется
> согласно order by, а потом тупо и грязно вытаскиваются необходимые данные.
> На самом деле, все можно делать по уму, т.е. использовать partial sort,
> например, в твоей задаче надо вытащить только 1 строчку, а про все остальные
> тебе совсем не важно, поэтому и сортировку можно остановить.
> Есть и еще алгоритмы.  А ключевым словом, к твоей задаче является
> 'top-k query' и на этк тему написаноо куча работ. Мы с Федей Сигаевым
> года три назад даже патч сделали, но тогда его не приняли из-за его
> плохой реализации.

Хорошо - посмотрю :( Как-то не очень оптимистично.

С уважением
    Евгений