помогите оптимизировать алгоритм

Axel · Сообщение **Axel** » 25 сен 2005, 13:37

суть проблемы такова:
есть таблица с объектами. объекты могут быть потомками других объектов из этой же таблицы (в поле "Parent ID" указан "ID" объекта-родителя).
нужно построить список объектов (достаточно только их "ID") таких которые так или инача удовлетворяют некоторым условиям (условия описаны в этой же таблице в конкретных полях).
Объясняю термин "так или иначе". Здесь я имею ввиду следующее. Если какой либо объект удовлетворяет условию, то считается, что все его предки так же удовлетворяют условию. При этом список должен быть построен в следующем порядке: добрались до низа ветки, ищем ближайшее сверху разветвление и идем опять вниз и т.д.
Так как я отличаюсь косноязычием, приведу пример.
допустим таблица имеет вид:
"ID" "Parent ID" "какое-то условие"
1 1 1
2 1 1
3 1 2
4 2 1
5 4 2
6 3 1
7 2 1
Тогда набор объектов для (условие = 1) будет: 1,2,4,7,3,6 (объект 3 попал в список так, как объект 6, для которого он является родителем, удовлетворяет условию). Для (условие = 2) набор объектов будет: 1,2,4,5,3. 4 попал из-за 5, в свою очередь 2 из-за 4, а 1 из=за 2 либо из-за 3.

Алгоритм предложенный мной заключается в следующем (реализован средствами хранимых процедур):
1. строю список "основных объектов" (где "ID"="Parent ID")
2. для каждого из них рекурсивно получаю потомков и проверяю удовлетворяет ли этот потомок "так или иначе" условию. если да, то suspend.

проверка на удовлетворение "так или иначе" условию заключается в подсчете всех потомков данного объекта, удовлетворяющего условию. если count>0, то объект "так или иначе" удовлетворяет условию. (отдельная процедура).

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

Подскажите что-нибудь разумное вплане оптимизации предложенного алгоритма или может кто опишет принципиально иной, но более оптимальный. Буду очень ждать.
заранее благодарен.

Axel · Сообщение **Axel** » 26 сен 2005, 12:57

при 250 000 записей в таблице время выполнения процедуры 7 сек. Это просто Ж...ПА какая-то. Что делать, как быть?

Dimitry Sibiryakov

Axel писал(а):Что делать, как быть?

Как насчет изменить структуру таблицы? Если каким-то (из двух мне извустных) способом свести выборку всех родителей записи к одному запросу, сам запрос сводится к self-join и конечным условиям.

eugeney · Сообщение **eugeney** » 26 сен 2005, 16:32

Axel писал(а):при 250 000 записей в таблице время выполнения процедуры 7 сек. Это просто Ж...ПА какая-то. Что делать, как быть?

Индексы есть?
В IBExpert'е смотрел статику чтений, для таблици? Сколько индексированных сколько не индексированных.
ПРиведи текст запроса и текст SP.

eugeney · Сообщение **eugeney** » 26 сен 2005, 16:33

Dimitry Sibiryakov писал(а):
Axel писал(а):Что делать, как быть?
Как насчет изменить структуру таблицы? Если каким-то (из двух мне извустных) способом свести выборку всех родителей записи к одному запросу, сам запрос сводится к self-join и конечным условиям.

Можно список способов?

Axel · Сообщение **Axel** » 26 сен 2005, 18:32

eugeney писал(а):ПРиведи текст запроса и текст SP.

Запрос, например, такой:
select "Event ID" from "Get list"(-20,310,'1.10.2005','1.9.2005')

скрипт ХП:

Код: Выделить всё

CREATE PROCEDURE "Get list" (
    "Dept ID" INTEGER,
    "Plan type ID" INTEGER,
    "Current date" TIMESTAMP,
    "Previous date" TIMESTAMP)
RETURNS (
    "Event ID" INTEGER,
    "Performer ID" INTEGER,
    "Event root" SMALLINT)
AS
DECLARE VARIABLE "count" INTEGER;
begin
  "Event root"=0;
  for
    select "ID", "Performer ID" from "Plan events"
    where (("Performance control date" < : "Current date" and "Performance date" is null)
    or ("Performance control date" < : "Current date" and "Performance control date" >= : "Previous date"
    and "Performance date" is not null)) and "ID" = "Parent ID" and "Plan type ID" = : "Plan type ID"
    into : "Event ID", : "Performer ID"
  do
  begin
    select count("ID") from "Get subjects of both groups"(: "Performer ID",: "Dept ID")
    into : "count";
    if ("count">0) then
    begin
        "Event root"=1;
        suspend;
    end
    else
    begin
        select count("Child event ID") from "Get child list of plan event"(: "Event ID", : "Dept ID")
        into : "count";
        if ("count">0) then
        begin
            "Event root"=1;
            suspend;
        end
    end
    if ("Event root">0) then
    begin
        for
            select "Child event ID" from "Get child list"(: "Event ID", : "Dept ID")
            into : "Event ID"
        do
        begin
            "Event root"=0;
            suspend;
        end
    end

  end
end

CREATE PROCEDURE "Get subjects of both groups" (
    "First subject ID" INTEGER,
    "Second subject ID" INTEGER)
RETURNS (
    ID INTEGER)
AS
begin
  for
      select f."ID" from "Get subject childrens"(: "First subject ID") f, "Get subject childrens"(: "Second subject ID") s
      where f."ID" = s."ID"
      into : "ID"
  do
  begin
      suspend;
  end
end

CREATE PROCEDURE "Get subject childrens" (
    "Current ID" INTEGER)
RETURNS (
    ID INTEGER)
AS
begin
  if ("Current ID">0) then
  begin
      for
        select "User ID" from "Users" where "User ID" = : "Current ID"
        into : "ID"
      do
      begin
        suspend;
      end
  end
  else
  begin
      for
        select "User ID" from "Users in groups" where "Group ID" = : "Current ID"
        into : "ID"
      do
      begin
        suspend;
      end
      for
        select "Group ID" from "Groups" where "Group ID" <> "Parent ID" and "Parent ID" = : "Current ID"
        into : "ID"
      do
      begin
            suspend;
            for
                select "ID" from "Get subject childrens"(: "ID")
                into : "ID"
            do
            begin
                suspend;
            end
      end
  end
end

CREATE PROCEDURE "Get child list of plan event" (
    "Parent event ID" INTEGER,
    "Dept ID" INTEGER)
RETURNS (
    "Child event ID" INTEGER)
AS
DECLARE VARIABLE "Performer ID" INTEGER;
DECLARE VARIABLE "Event ID" INTEGER;
DECLARE VARIABLE "count" INTEGER;
DECLARE VARIABLE "temp count" INTEGER;
begin
  for
    select "ID", "Performer ID" from "Plan events"
    where "Parent ID" = : "Parent event ID" and "ID" <> "Parent ID"
    into : "Child event ID", : "Performer ID"
  do
  begin
    "count" = 0;
    select count("ID") from "Get subjects of both groups"(: "Performer ID", : "Dept ID")
    into : "temp count";
    if ("temp count">0) then
    begin
        "count" = "count" + "temp count";
    end
    else
    begin
        for select "Event ID" from "Get event subtree"(: "Child event ID")
            into : "Event ID"
        do
        begin
            select count("ID") from "Get subjects of both groups"((select "Performer ID" from "Plan events" where "ID" = : "Event ID"), : "Dept ID")
            into : "temp count";
            "count" = "count" + "temp count";
        end
    end
    if ("count">0) then
    begin
        suspend;
    end
  end
end

CREATE PROCEDURE "Get event subtree" (
    "Parent ID" INTEGER)
RETURNS (
    "Event ID" INTEGER)
AS
begin
  for
    select "ID" from "Plan events" where "Parent ID" = : "Parent ID" and "ID" <> "Parent ID"
    into : "Event ID"
  do
  begin
    suspend;
    for
        select "Event ID" from "Get event subtree"(: "Event ID")
        into : "Event ID"
    do
    begin
        suspend;
    end
  end
end

CREATE PROCEDURE "Get child list" (
    "Parent event ID" INTEGER,
    "Dept ID" INTEGER)
RETURNS (
    "Child event ID" INTEGER)
AS
begin
  for
    select "Child event ID" from "Get child list of plan event"(: "Parent event ID",: "Dept ID")
    into : "Child event ID"
  do
  begin
    suspend;
    for select "Child event ID" from "Get child list"(: "Child event ID",: "Dept ID")
        into : "Child event ID"
    do
        suspend;
  end
end

таблицы (правда, без ключей, тригеров и генераторов, а то и так много текста выходит. стоит только отметить, что ID в таблице Users положительные, а в таблице Groups отрицательные - так надо было :) ):

CREATE TABLE "Plan events" (
    ID                          ID NOT NULL /* ID = INTEGER NOT NULL */,
    "Parent ID"                 ID NOT NULL /* ID = INTEGER NOT NULL */,
    "Plan type ID"              ID NOT NULL /* ID = INTEGER NOT NULL */,
    "Author ID"                 ID /* ID = INTEGER NOT NULL */,
    "Record date"               TIMESTAMP,
    "Performer ID"              ID /* ID = INTEGER NOT NULL */,
    "Performance control date"  TIMESTAMP,
    "Performance date"          TIMESTAMP
);

CREATE TABLE "Users" (
    "User ID"       ID /* ID = INTEGER NOT NULL */,
    "Login"         "Login" /* "Login" = VARCHAR(31) NOT NULL */,
    "Time expired"  DATE,
    "Audit"         "Boolean" DEFAULT 1 NOT NULL /* "Boolean" = SMALLINT DEFAULT 0 CHECK (VALUE BETWEEN 0 AND 1) */,
    "Multisession"  "Boolean" DEFAULT 0 NOT NULL /* "Boolean" = SMALLINT DEFAULT 0 CHECK (VALUE BETWEEN 0 AND 1) */,
    "First name"    "Name" /* "Name" = VARCHAR(25) NOT NULL */,
    "Middle name"   "Name" /* "Name" = VARCHAR(25) NOT NULL */,
    "Last name"     "Name" /* "Name" = VARCHAR(25) NOT NULL */,
    "Birthday"      DATE,
    "Note"          "Note" /* "Note" = VARCHAR(32000) */,
    "Initials"      COMPUTED BY (Substring("Middle name" from 1 for 1)||'.'||Substring("Last name" from 1 for 1)||'.')
);

CREATE TABLE "Groups" (
    "Group ID"      ID NOT NULL /* ID = INTEGER NOT NULL */,
    "Parent ID"     ID /* ID = INTEGER NOT NULL */,
    "Name"          "Name medium" /* "Name medium" = VARCHAR(50) */,
    "Short name"    "Name" /* "Name" = VARCHAR(25) NOT NULL */,
    "Full name"     "Name large" /* "Name large" = VARCHAR(100) */,
    "Time expired"  DATE,
    "Audit"         "Boolean" DEFAULT 1 NOT NULL /* "Boolean" = SMALLINT DEFAULT 0 CHECK (VALUE BETWEEN 0 AND 1) */,
    "Order"         "Unsigned integer" /* "Unsigned integer" = INTEGER CHECK (Value>=0) */,
    "Note"          "Note" /* "Note" = VARCHAR(32000) */
);

CREATE TABLE "Users in groups" (
    "User ID"   ID NOT NULL /* ID = INTEGER NOT NULL */,
    "Group ID"  ID NOT NULL /* ID = INTEGER NOT NULL */,
    "Order"     "Unsigned integer" DEFAULT 10 NOT NULL /* "Unsigned integer" = INTEGER CHECK (Value>=0) */
);

Вроде ничего не забыл. Если будет чего нехватать, скажите - добавлю.
Да таблицы Users, Groups и Users in groups сравнительно маленькие по количеству записей, а вот Plan events - будет большой. Удалять записи из этой таблицы можно только двух летней давности, т.е. в текущем году я должен иметь возможность просматривать event'ы всего прошлого года.

Сообщение **kdv** » 26 сен 2005, 19:32

первое - вызов процедур из процедур и count из процедур - это, конечно, "типа круто", но надо понимать, что все это выполняется как в любом ЯП - тупо последовательно, и никакой оптимизации не подлежит. Сервер может оптимизировать только запросы select (и update/delete, но это к делу не относится).

так что, не вникая особо во все странности кода, полагаю, в нынешнем варианте соптимизировать удастся только какие то куски, но не весь принцип целиком. Статью Котляревского на сайте читал?