Производительность рекурсивной обработки данных с использованием Java и SQLite

Question

Если у вас есть ответ, не связанный с Java / SQLite, я с удовольствием его прочту.

Окружающая среда

Я храню предметы в базе данных по следующей схеме:

###################
#       Item      #    
###################
#      _id        #    This is the primary key
#    parent_id    #    If set, it the ID of the item containing this item
#      date       #    An ordinary date
#  geocontext_id  #    Foreign key to a pair of named coordinates
###################

###################
#   Geocontext    #    
###################
#       _id       #    This is the primary key
#       name      #    Way for the user to label a pair of coordinates (e.g : "home", "work")
#         x       #    One of the coordinate
#         y       #    The other one
###################

Проблема

Я должен отфильтровать элементы по геоконтексту и дате. Было бы легко, если бы все предметы были на одном уровне, но дело в том, что это рекурсивно. E.G:

root
      |_item 1
      |_item 2 
      |      |_item 4
      |      |_item 5
      |             |_item 6
      |_item 3
      |      |_item 8
      |             |_item 10
      |_item 11
      |       |_item 12
      |_item 7

Нет явного ограничения рекурсивной глубины.

Теперь, если мы находимся в каком-либо узле и фильтруем по дате «1 апреля», мы должны видеть не только элементы, непосредственно содержащиеся в узле, которые соответствуют дате, но мы должны видеть элементы, которые содержат элементы, соответствующие дате также .

E.G: Мы находимся в «Элементах 2», если «элемент 6» совпадает с датой, то мы считаем, что «элемент 5» также совпадает с датой, и мы должны сохранить ее. Если мы находимся в корне, то пункт 2 должен отображаться.

То же самое касается геоконтекста, но это еще сложнее, потому что:

• Он хранится в другой таблице.
• Сопоставление с контекстом является дорогостоящим математическим вычислением.

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

ПРИМЕЧАНИЕ: Мне не нужно отображать дерево . Я отображаю список отфильтрованных данных из дерева. Мы должны видеть только плоский список верхних элементов. Задача состоит в том, чтобы решить, отображать ли каждый элемент или нет, в соответствии со всеми иерархиями детей.

Как я пытался это решить

Я думал, что смогу немного облегчить проблему, используя больше таблиц для кэширования плоских данных:

###################
# Geocontex_cache #    
###################
#     item_id     #     I can Join the items table on this field
#     child_id    #     I can delete / update a child, and so delete / update the cache
#  geocontext_id  #     I can delete / update a geocontext, and so delete / update the cache
#        x        #      Here, I can brute force :-)
#        y        # 
###################

###################
#    Date_cache   #    
###################
#     item_id     #     
#     child_id    #    
#       date      #    
###################

Это кажется разумным, но я еще не пробовал. Тем не менее, он должен иметь следующие недостатки:

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

• Размер базы данных может стать огромным. Уровень глубины пять хранилище данных в кеше для пяти родители. Не знаю, актуально ли это, так как это однопользовательское приложение с ручной ввод. Я никого не думаю вставит более 1000 наименований с уровнем глубины более 10

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

Теперь мой вопрос

Как бы вы хранили данные и обрабатывали фильтрацию наиболее оптимальным способом?

Дополнительно:

Должен ли я определить явный рекурсивный предел глубины? Должен ли я выполнять фильтрацию с использованием SQL или Java? SQL, безусловно, будет быстрее, но сопоставление геоконтекста намного проще в Java.

Поскольку я работаю на платформе Android, у меня есть следующие ограничения:

• Java - единственный доступный язык, а не со всей стандартной библиотекой.

• SQLite - единственная доступная СУБД.

• Производительность и память важны проблемы. Если вам нужно выбрать, срок службы батареи и, следовательно, производительность является приоритетом.

• Экзотические внешние библиотеки не могут быть в состоянии для использования.

P.S: Я покопался в SO и нашел несколько интересных фрагментов информации (особенно Какой самый эффективный / элегантный способ разбить плоский стол на дерево? ). Это подсказка, но не решение проблем.

Answer 1

1) Во-первых, давайте посмотрим, как просто поместить все в память. Это простое, гибкое и, прежде всего, быстрое решение. Недостатки включают в себя тот факт, что вам придется читать все в память при запуске (дать пользователю симпатичную полосу загрузки, а они даже не заметят), и, возможно, придется немного проделать дополнительную работу, чтобы все отражалось на диске, когда пользователь думает, что это так, чтобы данные не терялись.

В этом анализе я делаю некоторые общие предположения об Android / Dalvik, о которых я не очень-то знаю, так что, надеюсь, это несколько точно :) Помните, что G1 имеет 192 МБ ОЗУ. Кроме того, ваше предположение выше было максимум около 1000 пунктов.

Object superclass ~ 8 bytes
parent/child pointer ~ 4 bytes
date (long) ~ 8 bytes
name (non interned string avg 32 chars) ~ 64 bytes
x point (int) ~ 4 bytes
y point (int) ~ 4 bytes

Total = 92 bytes + possible memory alignment + fudge factor = 128 bytes
1000 items = 125kB
10000 items = 1.22MB

Примечание: я понимаю, что, хотя у ребенка может быть только один указатель, у родителя может быть несколько детей. Однако количество указателей parent-> child равно (elements - 1), поэтому средняя стоимость указателя parent-> child составляет (elements - 1) / elements ~ 1 element или 4 байта. Это предполагает дочернюю структуру, которая не выделяет неиспользуемую память, такую ​​как LinkedList (в отличие от ArrayList)

2) Болван во мне говорит, что это было бы забавное место для профилирования дерева B +, но я думаю, что это излишне для того, что вы хотите в данный момент :) Однако, какое бы решение вы ни выбрали Если вы не храните все в памяти, вы наверняка захотите кэшировать как можно больше верхних уровней дерева в памяти. Это может резко сократить количество дисковой активности.

3) Если вы не хотите использовать всю память, другое возможное решение может быть следующим. Билл Карвин предлагает довольно элегантную структуру RDBMS, называемую Closure Table , для оптимизации операций чтения на основе дерева, в то же время делая запись более сложной. Объединение этого с кэшем верхнего уровня может дать вам преимущества в производительности, хотя я бы проверил это, прежде чем поверить на это:

При оценке представления используйте все, что у вас есть в памяти, чтобы оценить как можно больше детей. Для тех дочерних элементов, которые не совпадают, используйте SQL-соединение между таблицей замыканий и плоской таблицей с соответствующим предложением where, чтобы выяснить, есть ли какие-либо совпадающие дочерние элементы. Если это так, вы будете отображать этот узел в списке результатов.

Надеюсь, все это имеет смысл и кажется, что это будет работать для того, что вам нужно.

Answer 2

Я слушал Soonil и попробовал «закрытие стола». Я добавил следующую таблицу:

################
#   Closure    #
################
# ancestor_id  #
#   item_id    #
################

Если, как и я, вы никогда не использовали эту модель раньше, она работает следующим образом:

Вы добавляете строку для каждого прямого или косвенного отношения в иерархии. Если C - ребенок B, а B - ребенок A, у вас есть:

ancestor    item
   B         C
   A         B
   A         C      # you add the indirect relationship   
   A         A
   B         B
   C         C      # don't forget any item is in relation with himself 

Тем не менее, с этой схемой вам не хватает важной информации: каковы прямые отношения? Что делать, если вам нужны только прямые потомки элемента?

Для этого вы можете добавить столбец is_direct с логическим значением в таблице закрытия или просто оставить столбец parent_id в таблице item. Это то, что я сделал, потому что это мешает мне переписать большую часть моего предыдущего кода.

Приятно то, что теперь я могу проверить, соответствует ли элемент дате или геоконтексту в одном запросе.

E.G, если я просматриваю все элементы, содержащиеся в элементе № 4, и хочу получить только те элементы, которые соответствуют или содержат дочерние элементы, соответствующие дате D:

SELECT ti.parent_id, ti.id, ti.title 
FROM item AS di                                  # item to filter with the date
              JOIN closure AS c                  # closure table
                  ON (di.id = c.item_id) 
              JOIN item AS ti 
                  ON (c.ancestor_id = ti.id)     # top item to display
WHERE di.date = D                                # here you filter by date   
AND ti.parent_id = 4                             # here you ensure you got only the top items

Так что я могу выбросить все свои *_cache таблицы. У меня все еще есть много работы, чтобы сделать один ОБНОВЛЕНИЕ / УДАЛЕНИЕ / СОЗДАТЬ , но все централизовано, и большая часть этого является процедурной, а не рекурсивной. Довольно круто.

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

Люблю этот трюк SQL, спасибо большое, ребята! На первый взгляд это немного сложно, но так очевидно, как только вы это сделаете.

Answer 3

Это может быть оффтоп, но ... вы рассматривали возможность использования сериализации?

Буферы протокола Google могут быть использованы для очень эффективной сериализации данных (время и пространство), вам нужно будет создать подходящую древовидную структуру (посмотрите в любой книге по CS), чтобы помочь с поиском. *

Я упомянул буферы протокола, потому что, будучи библиотекой Google, они могут быть доступны на Android.

Просто мысль.

Answer 4

AFAICT вы можете использовать иерархические запросы (Google для "CONNECT BY" "НАЧАТЬ С") в SQLite ...