Как бы вы реализовывали следующий запрос, если бы вы вам пришлось писать базу данных?

SELECT datetime from m_geo_position where datetime>1009794282 order by datetime LIMIT 2 OFFSET 600000

Более конкретно: есть набор записей с прямым доступом. Есть поле на которое можно наложить бинарный индекс.
И есть запрос у кторого может быть сортировка, фильтрация и LIMIT
Что делать если фильтров несколько и сортировка по нескольким полям? И фильтры не совпадают с сортировкой.
Что-то у меня крышу рвёт с оптимизацией этого дела.
Т.е. в каком порядке я что должен делать.
Такая задача становиться при чтении больших плоских файлов. У которых сбоку может быть индекс на поле.
Т.к. файлы большие желательно их не грузить в память целиком, а тупой лимит с сортировкой, по моему,
обязывает хранить OFFSET+LIMIT записей в мозгах и проходить весь файл.

Сейчас я сначала накладываю фильтр, потом выбираю необходимые записи, потом сортиртирую.
У меня сейчас только предположение что надо после фильтрации выбирать весь индекс по чортируемому полю,
смотреть какие записи в него попали, на попавшие записи накладывать LIMIT???

Я смотрел как с подобным справляется Postgress.
У меня есть таблица 611167 записей

                       "public.m_geo_position"
 en              | integer          | not null
 sig             | integer          | default 0
 datetime        | double precision | default float8((abstime(now()))::integer)
    "m_geo_position_pkey" ключевое поле, btree (en)
    "m_geo_position_datetime_idx" btree (datetime)

Вот такие запросы и их explain

select en from m_geo_position order by en LIMIT 2 OFFSET 600000; ~5sec.
 Limit  (cost=21311.44..21311.44 rows=1 width=4)
   ->  Index Scan using m_geo_position_pkey on m_geo_position  (cost=0.00..21311.44 rows=531920 width=4)

select datetime from m_geo_position order by datetime LIMIT 2 OFFSET 600000; ~5sec.
 Limit  (cost=44553.94..44553.94 rows=1 width=8)
   ->  Index Scan using m_geo_position_datetime_idx on m_geo_position  (cost=0.00..44553.94 rows=531920 width=8)

никакой попытки сделать объеденения по ключам???
select datetime,en from m_geo_position order by datetime,en LIMIT 2 OFFSET 600000; ~10sec.
 Limit  (cost=85336.85..85336.85 rows=1 width=12)
   ->  Sort  (cost=84007.05..85336.85 rows=531920 width=12)
         Sort Key: datetime, en
         ->  Seq Scan on m_geo_position  (cost=0.00..14039.20 rows=531920 width=12)

опять ничем не пользуемся
select en,datetime from m_geo_position order by en,datetime LIMIT 2 OFFSET 600000; ~7.5sec.
 Limit  (cost=85336.85..85336.85 rows=1 width=12)
   ->  Sort  (cost=84007.05..85336.85 rows=531920 width=12)
         Sort Key: en, datetime
         ->  Seq Scan on m_geo_position  (cost=0.00..14039.20 rows=531920 width=12)

сначала отфильтровали потом тоже самое
select en,datetime from m_geo_position where datetime>1009795282 order by en,datetime LIMIT 2 OFFSET 600000; ~8sec.
   ->  Sort  (cost=85331.43..86661.10 rows=531867 width=12)
         Sort Key: en, datetime
         ->  Seq Scan on m_geo_position  (cost=0.00..15369.00 rows=531867 width=12)
               Filter: (datetime > 1009795282::double precision)

о каким то образом заюзали индексы
select datetime from m_geo_position where datetime>1009795282 order by datetime LIMIT 2 OFFSET 600000; ~5sec.
 Limit  (cost=45880.16..45880.16 rows=1 width=8)
   ->  Index Scan using m_geo_position_datetime_idx on m_geo_position  (cost=0.00..45880.16 rows=531867 width=8)
         Index Cond: (datetime > 1009795282::double precision)

тоже самое по полю без индексов
select sig from m_geo_position where sig>0 order by sig LIMIT 2 OFFSET 600000; ~14sec.
 Limit  (cost=81461.52..81461.52 rows=1 width=4)
   ->  Sort  (cost=80131.84..81461.52 rows=531871 width=4)
         Sort Key: sig
         ->  Seq Scan on m_geo_position  (cost=0.00..15369.00 rows=531871 width=4)
               Filter: (sig > 0)

Здравствуйте, <Аноним>, Вы писали:

А>Как бы вы реализовывали следующий запрос, если бы вы вам пришлось писать базу данных?
А>

А>SELECT datetime from m_geo_position where datetime>1009794282 order by datetime LIMIT 2 OFFSET 600000
А>

Тут все банально и просто. Предположим, у нас B-Tree по datetime ( в противном случае это table scan).
1. Спускаемся по индексу до листа с >100979428
2. Выполняем SKIP 600000 — это довольно-таки быстро, особенно если хранить количества листьев в узлах.
3. Выводим 2 значения даты.

А>Более конкретно: есть набор записей с прямым доступом. Есть поле на которое можно наложить бинарный индекс.
А>И есть запрос у кторого может быть сортировка, фильтрация и LIMIT
А>Что делать если фильтров несколько и сортировка по нескольким полям? И фильтры не совпадают с сортировкой.
А>Что-то у меня крышу рвёт с оптимизацией этого дела.
1. Оптимизируй фильтр.
Для этого сравни все предикаты с имеющимися индексами. Например, выбираем по a=6 and b>5. Есть индексы по а, по b, и по (a, b).
План 1: seek idx_a (=6) -> bookmark lookup (b) -> filter(b>5)
План 2: seek idx_b (>5) -> bookmark lookup (a) -> filter(a=6)
План 3: seek idx_ab (> (6, 5))
Оценивая стоимость каждого плана, поймешь, какой дешевле.
2. Оптимизируй сортировку. Если выход предыдущего плана не совпадает по сортировке, то надо будет добавить sort. Допустим, мы сортируем по b:
План 1: seek idx_a (=6) -> bookmark lookup (b) -> filter(b>5) -> sort(b)
План 2: seek idx_b (>5) -> bookmark lookup (a) -> filter(a=6)
План 3: seek idx_ab (> (6, 5)) -> sort(b)
3. На лимит забей.

А>Т.е. в каком порядке я что должен делать.
Ну, для начала
0. Купи книгу типа этой

Автор(ы): Гектор Гарсиа-Молина, Джеффри Ульман, Дженнифер Уидом
Издательство: Вильямс
Цена: 424р.

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

и внимательно изучи.

А>Я смотрел как с подобным справляется Postgress.
А>У меня есть таблица 611167 записей
А>

А>                       "public.m_geo_position"
А> en              | integer          | not null
А> sig             | integer          | default 0
А> datetime        | double precision | default float8((abstime(now()))::integer)
А>    "m_geo_position_pkey" ключевое поле, btree (en)
А>    "m_geo_position_datetime_idx" btree (datetime)
А>

А>Вот такие запросы и их explain

А>никакой попытки сделать объеденения по ключам???
А и не выйдет. Нужен композитный индекс.
А>опять ничем не пользуемся
По той же причине.
А>сначала отфильтровали потом тоже самое
Фильтруешь по "хвосту" сортировки.
А>о каким то образом заюзали индексы
Потому как не надо ничего больше сканировать. Все идет по одному полю, которое по совместительству является ключом индекса m_geo_position_datetime_idx
А>тоже самое по полю без индексов