Как создать индексированную таблицу?

Question

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

table.select do 
    age > 44 
    name == "Adam" 
end 

и производит кучу экземпляров Condition класса, как EqCondition, GteCondition и т.д. Ну, это легкая часть. Table проверяет эти условия и выбирает соответствующий индекс для выполнения запроса. Что я застрял в том, какие параметры должны принимать Index#select? Если он принимает те же параметры, что и метод выбора таблицы, он делает то же самое дважды. Предположим, нам нужно выбрать всех с возрастом больше 25. Сначала класс Table определяет, что существует индекс (age, name), который может быть использован. Затем индекс должен определить, что это запрос диапазона, включающий только часть ключа и выполняющий его соответственно.

Я спрашиваю о некоторых идеях о том, как правильно спроектировать (возможно, какая-то более простая версия того, как это делается в реальных базах данных)?

PS. Это Рубин, но я думаю, что это не актуально. В Java/C# это будет выглядеть как table.select(new GtCondition("age", 44), new EqCondition("name", "Adam"))

Answer 1

принять во внимание, что цель индексов на СУБД:

• уменьшить IO
• оптимизировать присоединяется
• и как побочный эффект: чтобы помочь соблюдения некоторых ограничений (например, PK/FK)

Когда ваш работают со всеми данными в оперативной памяти, иногда просто делает линейное сканирование достаточно :)

Если у вас есть сомнения, используйте профайлер ... и вы увидите, что в памяти в памяти можно сказать, что 1000 элементов крошечные. Если у вашего кода нет JOIN, использование простого collection.filter(condition), вероятно, достаточно хорошо.

Но как это работает с базами данных? Вот приблизительная идея:

• Сначала выражение SELECT преобразуется в «каноническое дерево». Например SELECT A.NAME,B.SOMETHING FROM A, B WHERE A.NAME=B.NAME AND B.OTHER > 10 может быть представлен в виде:

  PROJECT(A.NAME, B.SOMETHING) 
        | 
  FILTER(A.NAME=B.NAME, B.OTHER>10) 
        | 
      CARTESIAN PRODUCT 
      |    | 
  PROJECT(A.NAME)  PROJECT(B.OTHER,B.SOMETHING) 
  

• Из этого дерева выражения есть некоторые алгебраические правила, чем могут быть применены. Цель состоит в том, чтобы избежать декартово произведение, так как это очень неэффективно:

  PROJECT(A.NAME, B.SOMETHING) 
        | 
      EQ-JOIN A,B USING NAME 
      |    | 
  PROJECT(A.NAME)  FILTER B.OTHER>10  
          | 
       PROJECT(B.OTHER,B.SOMETHING) 
  

• двигатель СУБД анализирует дерево и метаданные базы данных (например, вида индексов, количество записей), и изменяет дерево оптимизировать его (то есть план запроса). Например, если B сортируется OTHER, лучше сделать ФИЛЬТР первым:

  PROJECT(A.NAME, B.SOMETHING) 
        | 
      EQ-JOIN A,B USING NAME (NESTED LOOP JOIN) 
      |    | 
  PROJECT(A.NAME) PROJECT(B.OTHER,B.SOMETHING) 
          | 
          FILTER B.OTHER>10 (UNSING INDEX ON OTHER) 
  

• Но тогда, если вы сделаете это, и у вас есть буфера B в памяти, может быть, вы теряете индексную информацию, и вы не можете используйте индекс больше (и единственным вариантом для соединения является использование вложенного цикла).Таким образом, двигатель может обнаружить, что и выбрать лучший план, может быть:

  PROJECT(A.NAME, B.SOMETHING) 
        | 
      FILTER B.OTHER>10 
        | 
      EQ-JOIN A,B USING NAME (HASH INDEX EQ-JOIN) 
      |    | 
  PROJECT(A.NAME) PROJECT(B.OTHER,B.SOMETHING) 
  

После того, что план будет готов. Это похоже на программу: двигатель следит за ней слепо.

Как вы можете использовать это для двигателя с памятью? Вы можете обнаружить EQUI JOINS и преобразовать «план» для использования хеш-таблицы. Возможно, вы можете использовать сбалансированное дерево для реализации других типов индексов, но, вероятно, это не слишком помогает: алгоритм O (n) в памяти прекрасен, это порядок O (nxm), который вы должны избегать, и это означает, что вы избегаете декартовой продукции.

эвристики, что вы можете сделать это: (т. Е имя == «Адам»)

• Обнаружить все одинаковые фильтры, и если таблица имеет индекс хэш-поле ... сначала используйте его, например: table.findUsingHash('name', 'Adam').

• Затем просто сканировать и фильтровать результаты (т.е. возраст> 44): filter(table.findUsingHash('name', 'Adam'), function (e) { return e.age > 44 })

Идея заключается в том, чтобы сделать наиболее селективный индекс первым, так что О (п) сканирования имеет небольшой п.

Примечание: Я не занимаюсь этим видом СУБД с давних времен. Поэтому мои диаграммы деревьев могут содержать некоторые ошибки ... обратитесь к книге СУБД (например, this) для лучшего источника.