Эффективный подход к массовому обновлению иерархической таблицы

У меня есть таблица базы данных, которая представляет собой иерархию файлов и каталогов со следующей структурой (упрощенной):

ItemId        int
Path          text
Type          int        (0 for files, 1 for directories)
ParentId      int
BackupTime    datetime

В настоящее время столбец BackupTime используется только для файлов, для каталогов он имеет значение null.

Теперь мне нужно заполнить этот столбец и для каталогов: это должно быть минимум BackupTime всех потомков (файлов и каталогов).

Этот (наивный и неэффективный) запрос иллюстрирует то, что я хочу сделать:

update Items i
set BackupTime = (select min(BackupTime)
                  from Items d
                  where d.Path like i.Path || '%'
                  and d.Type = 0)
where i.Type = 1

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

Вероятно, было бы быстрее искать min(BackupTime) только по прямым дочерним элементам:

update Items i
set BackupTime = (select min(BackupTime)
                  from Items d
                  where d.ParentId = i.ItemId)
where i.Type = 1

Но чтобы это работало, я должен гарантировать, что потомки будут обновляться раньше, чем их предки, поэтому я должен рекурсивно проходить иерархию снизу вверх. Проблема в том, что у меня нет простого способа узнать, какие элементы являются самыми глубокими в иерархии. Я использую SQLite, поэтому не могу использовать иерархические запросы.

Любая идея о том, как сделать это эффективно?

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


sql optimization performance hierarchy hierarchical-data
person Thomas Levesque    schedule 26.04.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Это выстрел в темноте, но он может сработать. Это попытка решить восходящую проблему вручную. (Я не знаю ограничений sqlite, но это, вероятно, стандартный SQL-92 и, надеюсь, все в порядке.)

Шаг 1: Решите, как вы хотите обрабатывать пустые каталоги. Я думаю, что решение здесь работает только в том случае, если нет пустых каталогов или если пустые каталоги изначально обновляются, поэтому у них есть искусственное время резервного копирования, отличное от NULL. (Важно то, каким должен быть этот искусственный BackupTime, в зависимости от того, как вы поддерживаете столбец BackupDate, когда в ваши данные вносятся изменения. Использование текущей даты или искусственной даты в будущем может сработать, но вы должны подумать об этом.)

Шаг 2. Выполняйте следующий запрос несколько раз, пока не будут затронуты все строки:

  update Items i set
    BackupTime = (
      select min(BackupTime)
      from Items d
      where d.ParentId = i.ItemId
    )
  where i.Type = 1
  and i.BackupTime is null
  and not exists (
    select *
    from Items d
    where d.ParentId = i.ItemId
    and d.Type = 1
    and d.BackupTime is null
  )

Другими словами, обновляйте BackupTime для каталогов, когда вам нужно, а также получайте всю информацию: когда их BackupTime равно null и они не содержат подкаталогов, значение BackupTime которых также равно null.

Таким образом, при первом запуске он установит BackupTime для всех каталогов, которые не содержат подкаталогов, а только файлы. Во второй раз он установит BackupTime для каталогов, содержащих подкаталоги, но не подкаталогов.

Возможно, вы сможете решить проблему с пустым каталогом, установив для BackupTime значение «coalesce((select...),current_timestamp»).

person Steve Kass    schedule 26.04.2012
comment
ОК, обработка БД с 100 000 элементов заняла 5 секунд... это очень хорошо ;). Я пробовал с фиктивной базой данных, поэтому мне нужно проверить с реальной, чтобы быть уверенным, но я уверен, что она будет иметь аналогичную производительность. Кстати, последнее условие с not exists не обязательно: если есть ноль, min просто вернет ноль, поэтому в конечном итоге он даст тот же результат с меньшим количеством итераций (14 вместо 27 в моем тесте) - person Thomas Levesque; 27.04.2012
comment
MIN вернет NULL, если значения only равны NULL. MIN НЕ вернет NULL, если NULL и другие значения объединены. NOT EXISTS необходим, чтобы гарантировать, что итерации идут снизу вверх. Если вы удалите НЕ СУЩЕСТВУЕТ, вы получите неверный результат! Предположим, что /dir1/ содержит два элемента: 1) файл с BackupTime 4/12 и 2) каталог /dir2/, содержащий 1 файл с временем резервного копирования 4/9. Без NOT EXISTS /dir1/ получит неправильное BackupTime 4/12 во время первой итерации. С NOT EXISTS он будет ждать до следующей итерации. Чем меньше итераций вы видите, тем больше вы предлагаете эти неправильные ответы. - person Steve Kass; 27.04.2012
comment
вы правы, я ошибся... Думаю, прошло слишком много времени с тех пор, как я серьезно занимался SQL;) - person Thomas Levesque; 27.04.2012