---

Разделы На главную История денег и экономики История экономических знаний Формы безналичных денег Международные финансы Экономические концепции Экономические теории Экономика в реальной жизни Экономический анализ и интеграция Макроэкономика Экономика и социальное общество Социальная экономика Социология Кризисная экономика Инфляция в экономике Экономика зарубежных стран Иностранные деньги Государственное регулирование Бюджетная система Политическая экономия Политология Законы денег Налогообложение Аудит Банкротство Теория рынка Конкуренция Международная торговля Товарная биржа Нефть и газ на бирже Логистика Банки - услуги и операции Банки в России Банковский кредит Недвижимость Ипотека в банке Инвестирование Стратегии инвестирования Инвестиционные фонды Ценные бумаги Акции Вексель Облигации Опционы Фьючерсы Биржевая торговля Биржа Forex Фондовый рынок Фондовый рынок России Волны Эллиотта Теория фракталов Торговая теория Ганна Фибоначчи на бирже Графический анализ на бирже Паттерны Биржевой анализ "Крестики-нолики" Японские свечи Технический анализ Математика на бирже Фундаментальный анализ Биржевая торговля Стратегии торговли Механические торговые системы Программирование МТС Управление торговым капиталом Управление портфелем Управление риском Страхование Профессия трейдер Практический трейдинг Технологии инфосистем Информационный рынок Безопасность информации Криптология и криптография Реклама PR - Public Relations Маркетинг Финансовая система Начало бизнеса Предпринимательство Малый бизнес Микроэкономика Торговля Ценообразование Работа в Интернете Сайты, софт, дизайн Управление качеством Управление предприятием Производство продукции Стратегический менеджмент Учебники по менеджменту Системы и организации Теория систем Планирование Статистика финансов Управление персоналом Трудовые отношения Бухгалтерия «1С:Бухгалтерия» Управленческий учет Делопроизводство и офис Автоматизация делопроизводства Рынок труда Карьера Менеджер Лидерство и бизнес карьера Лидерство и карьера Общение и переговоры Общение в бизнесе Бизнес переговоры Инновации в моделировании Экономическое моделирование Нейронные сети Нейролингвистика Логика нейросетей Программирование Пакет Excel Технологии программирования Языки программирования Практическая психология Психологические тренинги Психология в медицине Возрастная психология Ваши скрытые резервы Здоровье и долголетие Работа с эмоциями Пикап Управление временем Гипнотерапия Подсознание Трансовые техники Магия Здоровье советы Спорт для здоровья Йога Религии Эзотерика Мистицизм

---

Обеспечение масштабируемости

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

Как мы покажем в разд. 6, средства разбиения графов хорошо масштабируются по отношению к числу разделов, но с ростом размера графа время их работы существенно возрастает. Поэтому мы сосредоточили усилия на уменьшении размеров графов. Интуитивно кажется, что это поможет уменьшить время работы алгоритма разделения, но ухудшит качество результата, поскольку входной граф меньшего размера содержит меньше информации. Однако мы разработали ряд эвристик, которые позволяют сократить размер графа с умеренным воздействием на качество разделения. Более точно, мы реализовали следующие эвристики:

• Взятие образцов на уровне транзакций (transaction-level sampling), что позволяет ограничить объем рабочей нагрузки, представляемой в графе, т.е. уменьшить число дуг.




• Взятие образцов на уровне кортежей (tuple-level sampling), что позволяет сократить число кортежей (узлов), представляемых в графе.




• Отбрасывание "ковровых" запросов (blanket statement filtering), что позволяет не учитывать редко встречающиеся запросы, приводящие к сканированию больших частей таблицы. Эта эвристика оправдывается тем, что (i) наличие таких запросов приводит к образованию в графе многих дуг, несущих мало информации, и (ii) выполнение подобных запросов эффективно распаллеливается по разделам, поскольку накладные расходы распределенных транзакций менее значительны, чем расходы на выполнение частей запроса в разных узлах.




• Фильтрация по релевантности (relevance filtering), когда удаляются кортежи, к которым обращения производятся очень редко (предельным случаем являются кортежи, к которым в рассматриваемой рабочей нагрузке вообще отсутствуют обращения).
  Соответствующие вершины графа мало информативны.



• 
  
  Звездообразная репликация (star-shaped replication), когда вершины-реплики связываются в звездообразную конфигурацию, а не в полный подграф (clique), что ограничивает число дуг.


• 
  
  Склеивание кортежей (tuple-coalescing), что позволяет представлять одной вершиной графа группу кортежей, к которым доступ всегда производится ко всем сразу. Это не вызывает потери информации и в некоторых случаях приводит к существенному сокращению размера графа.

Эти эвристики обеспечили эффективное сокращение размеров графов для наших тестовых наборов, сохранив при этом высокое качество результатов. Например, в подразделе 6.2 мы показываем, что (при наличии нескольких тысяч транзакций) в покрытии графа, включающем всего 0,5% от числа кортежей базы данных, остается достаточно информации, чтобы получить разделение, качество которого сопоставимо с наилучшим разделением базы данных, выполненным вручную.

---