Как эффективно выбрать случайную строку с помощью смещенной задачи. дистрибутив с Rails 2.3 и PostgreSQL 8? - PullRequest
1 голос
/ 06 сентября 2011

Я написал несколько простых приложений на Rails, получающих доступ к базе данных через абстракцию ActiveRecord, поэтому я боюсь, что не очень разбираюсь во внутренней работе движка PostgreSQL. Однако я пишу приложение на Rails, которое должно поддерживать более 100 000 строк с динамически обновляемым содержимым, и мне интересно, эффективно ли я использую случайные функции:

Database migration schema setting:
t.float: attribute1
t.integer: ticks

add_index :mytable, :attribute1
add_index :mytable, :ticks

В принципе, я хочу получить следующее распределение случайных функций:

a) строка с 10% -ным верхним значением в attribute1 = 30% вероятности выбора

b) средняя строка 60% (в attribute1) = 50% вероятности выбора

в) наименьший 30% (в атрибуте 1) с менее чем 100 тиками = 15% вероятности выбора,

d) и для тех, у кого атрибут 30% наименьший, у которых больше X (используйте X = 100 в этом вопросе), тики = 5% вероятности выбора.

На данный момент у меня есть следующий код:

@rand = rand()
if @rand>0.7
    @randRowNum = Integer(rand(0.1) * Mytable.count )
    @row = Mytable.find(:first, :offset =>@randRowNum , :order => '"attribute1" DESC')
else
    if @rand>0.2
        @randRowNum = Integer((rand(0.6)+0.1) * Mytable.count)
        @row= Mytable.find(:first, :offset =>@randRowNum , :order => '"attribute1" DESC')
    else
        @row= Mytable.find(:first, :offset =>Integer(0.7 * Mytable.count), :order => '"attribute1" DESC')
        if !(@row.nil?) 
            if (@rand >0.05)
                @row= Mytable.find(:first, :order => 'RANDOM()', :conditions => ['"attribute1" <= '"#{@row.attribute1}", '"ticks" < 100' ] )
            else
                @row= Mytable.find(:first, :order => 'RANDOM()', :conditions => ['"attribute1" <= '"#{@row.attribute1}", '"ticks" >= 100' ] )
            end
        end
    end
end

1) Я хотел бы избежать использования: order => 'RANDOM ()', поскольку, согласно моим исследованиям, кажется, что каждый раз, когда он вызывается, механизм SQL сначала сканирует все строк, присваивая им случайные значения. Отсюда использование @randRowNum = Integer (rand (0.1) * Mytable.count) и смещение @randRowNum. а) и б). Я действительно улучшаю эффективность? Есть ли лучший способ?

2) Должен ли я делать то же, что и 1) для c) и d), и использовать: условия => ['attribute1 "<='" #‹@row.attribute1} ", '" ticks "> = 100 '], заставляю ли я механизм SQL сканировать все строки? Есть ли что-то кроме индексации, что я могу повысить эффективность этого вызова (с минимально возможным объемом памяти и служебных данных)?

3) Существует вероятность того, что общее количество записей в Mytable могло быть изменено между вызовами Mytable.count и Mytable.find. Я мог бы поместить два вызова в транзакцию, но кажется чрезмерным заблокировать всю эту таблицу только для операции чтения (на данный момент у меня есть дополнительный код для возврата к простому случайному выбору строки, если я получил @ row.nil из приведенного выше кода). Возможно ли переместить этот вызов .count в один атомарный SQL-запрос в Rails? Или это будет так же эффективно, как блокировка транзакций в Rails?

4) Я также читал о хранимых процедурах в PostgreSQL ... но для этого конкретного случая есть ли какой-то выигрыш в эффективности, стоит ли переносить код из абстракции Activerecording в хранимые процедуры?

Большое спасибо!

P.S. среда разработки / развертывания: Рубе 1.8.7 Рельсы 2.3.14 PostgreSQL 8 (на Heroku)

Ответы [ 2 ]

1 голос
/ 09 сентября 2011

Ваш вопрос кажется немного расплывчатым, поэтому поправьте меня, если моя интерпретация неверна.

Если бы вы не разделяли (c) и (d), я просто преобразовал бы равномерную случайную переменную с [0,1) в смещенную случайную переменную с [0,1) и использовал ее для выбора смещения строки .

К сожалению, (c) и (d) разделены на основе значения «галочки» - другой столбец. Это сложная часть, которая также делает запрос намного менее эффективным.

После того, как вы извлечете значение attribute1 снизу на 70%, также получите количество (c) строк; что-то вроде SELECT COUNT(*) FROM foo WHERE attribute1 <= partiton_30 AND ticks < 100. Затем используйте это, чтобы найти смещение в случаях ticks < 100 или ticks >= 100. (Возможно, вы хотите индекс на (attribute1, ticks) или что-то еще; порядок, который лучше всего зависит от ваших данных).

Если пороговое значение «тиков» известно заранее и его не нужно часто менять, вы можете кэшировать его в столбце (BOOL ticks_above_threshold или в любом другом), что делает запрос намного более эффективным, если у вас есть индекс на (ticks_above_threshold, attribute1) (обратите внимание на разворот). Конечно, каждый раз, когда вы меняете порог, вам нужно записывать в каждую строку.

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

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

EDIT:

Чтобы ответить на ваши дополнительные вопросы:

  1. Индексирование (BOOL ticks_above_threshold, attribute1) должно работать лучше, чем (ticks, attribute1) (хотя у меня может быть неправильный порядок), потому что это позволяет сравнивать первый индексный столбец на равенство. Это важно.

    Индексы обычно используют какое-то сбалансированное дерево для поиска того, что фактически является списком. Например, возьмите A4 B2 C3 D1 (упорядоченная буква, число) и найдите «количество строк с буквой больше B и числом больше 2». Лучшее, что вы можете сделать, это начать после B и итерировать по всей таблице. Если вы заказываете по номеру, букве, вы получаете 1D 2B 3C 4A. Снова начните через 2 с.

    Если вместо этого ваш индекс находится на is_greater_than_2, буква, он выглядит как ложь, B ложь, D истина, A истина, C. Вы можете запросить индекс для позиции (true, B) - между true, A и true, C - и посчитать количество записей до конца. Подсчет количества элементов между двумя позициями индекса происходит быстро.

    Google App Engine Ограничения на запросы идет на один шаг дальше:

    Неравенство разрешено только для одного свойства

    В запросе могут использоваться фильтры неравенства (<, <=,> =,>,! =) Для одного свойства во всех его фильтрах.

    ...

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

  2. Если ни один из вас не использует индекс для ticks, тогда да.

    В некоторых случаях может быть быстрее индексировать a вместо a,b (или b,a), если предложение, включающее b, почти всегда верно, и вы выбираете данные строки (а не просто получаете COUNT()) (т. Е. Если 1000 <= a AND a <= 1010 соответствует миллиону строк и b > 100 дает сбой только для двух строк, то может быть быстрее выполнить два дополнительных поиска строк, чем работать с большим индексом). 1070 *

0 голосов
/ 09 сентября 2011

До тех пор, пока строки не удаляются с помощью вызова count () и вызова find (), я не буду беспокоиться о транзакциях. Определенно избавьтесь от упорядочивания всех вызовов с помощью RANDOM (), так как нет способа его оптимизировать. Убедитесь, что для attribute1 указан индекс. Я не проверял это, но что-то вроде этого должно быть довольно быстро:

total_rows = MyTable.count
r = rand()

if r > 0.7  # 90-100%
  lower = total_rows * 0.9
  upper = total_rows
elsif r > 0.2 # 30-89%
  lower = total_rows * 0.3
  upper = total_rows * 0.89
else # 0-29%
  lower = 0
  upper = total_rows * 0.29
end

offset = [lower + (upper - lower) * rand(), total_rows - 1].min.to_i

@row = Mytable.find(:first, :offset => offset, :order => 'attribute1 ASC')
...