О, эти планы запросов



    История стара как мир. Две таблицы:
    • Cities – 100 уникальных городов.
    • People – 10 млн. людей. У некоторых людей город может быть не указан.

    Распределение людей по городам – равномерное.
    Индексы на поля Cites.Id, Cites.Name, People .CityId – в наличии.

    Нужно выбрать первых 100 записей People, отсортированных по Cites.



    Засучив рукава, бодро пишем:

    select top 100 p.Name, c.Name as City from People p
    left join Cities c on c.Id=p.CityId
    order by c.Name


    При этом мы получим что-то вроде:



    За… 6 секунд. (MS SQL 2008 R2, i5 / 4Gb)

    Но как же так! Откуда 6 секунд?! Мы ведь знаем, что в первых 100 записях будет исключительно Алматы! Ведь записей – 10 миллионов, и значит на город приходится по 100 тыс. Даже если это и не так, мы ведь можем выбрать первый город в списке, и проверить, наберется ли у него хотя бы 100 жителей.

    Почему SQL сервер, обладая статистикой, не делает так:

    select * from People p
    left join Cities c on c.Id=p.CityId
    where p.CityId
    in (select top 1 id from Cities order by Name)
    order by c.[Name]

    Данный запрос возвращает примерно 100 тыс. записей менее чем за секунду! Убедились, что есть искомые 100 записей и отдали их очень-очень быстро.

    Однако MSSQL делает все по плану. А план у него, «чистый термояд» (с).


    Вопрос к знатокам:
    каким образом необходимо исправить SQL запрос или сделать какие-то действия над сервером, чтобы получить по первому запросу результат в 10 раз быстрее?


    P.S.
    CREATE TABLE [dbo].[People] (
    [Id] uniqueidentifier NOT NULL,
    [Name] nvarchar(50) NOT NULL,
    [CityId] uniqueidentifier
    )
    ON [PRIMARY]
    GO

    CREATE TABLE [dbo].[Cities] (
    [Id] uniqueidentifier NOT NULL,
    [Name] nvarchar(50) NOT NULL,
    )
    ON [PRIMARY]
    GO


    P.P.S
    Откуда растут ноги:
    Задача вполне реальная. Есть таблица с основной сущностью, от нее по принципу «звезда» отходит множество измерений. Пользователю нужно ее отобразить в гриде, предоставив сортировку по полям.
    Начиная с некоторого размера основной таблицы сортировка сводится к тому, что выбирается окно с одинаковыми (крайними) значениями, (вроде «Алматы») но при этом система начинает жутко тормозить.
    Хочется иметь ОДИН параметризированный запрос, который будет эффективно работать как с малым размером таблицы People так и с большим.

    P.P.P.S
    Интересно, что если бы City были бы NotNull и использовался InnerJoin то запрос выполняется мгновенно.
    Интересно, что ДАЖЕ ЕСЛИ поле City было бы NotNull но использовался LeftJoin – то запрос тормозит.

    В комментах идея: Сперва выбрать все InnerJoin а потом Union по Null значениям. Завтра проверю эту и остальные безумные идеи )

    P.P.P.P.S Попробовал. Сработало!

    WITH Help AS
    (
    select top 100 p.Name, c.Name as City from People p
    INNER join Cities c on c.Id=p.CityId
    order by c.Name ASC
    UNION
    select top 100 p.Name, NULL as City from People p
    WHERE p.CityId IS NULL
    )
    SELECT TOP 100 * FROM help

    Дает 150 миллисекунд при тех же условиях! Спасибо holem.
    Ads
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More

    Comments 142

      –55
      sphinx
        +10
        причем тут сфинкс, где тут полнотекстовый поиск?
          –22
          он отлично подходит не только для фултекста, но и для фильтрации и сортировки.
          • UFO just landed and posted this here
              –24
              он спрашивает как уменьшить время в 10 раз
                +17
                кажется, вы изрядно тупите
                  +12
                  Как обычно 3 способа решения проблемы со скоростью:
                  1. оптимизировать запрос (ниже там с иннер джоин предложили вариант, автор не отписался какое время выполнения стало)
                  2. увеличить ресурсы: больше памяти, круче железо
                  3. использовать другое ПО

                  я просто предложил третий вариант
                    +2
                    извините, если резко ответил в предыдущем комменте, но у автора поста вопрос не стоял в том, что «подскажите, какой ПО мне нужно использовать, чтобы уменьшить время выполнения этого запроса?»
                    он спросил: «как, используя текущее ПО, мне изменить _запрос_, чтобы он выполнялся быстрее
                    sphinx — крутая штука, несомненно, но не стоит уж из пушки по воробьям-то)
                      +2
                      третий вариант былбы использовать oracle вместо mssql
                      а так это совершенно разные задачи
            +5
            О, узнаю «паттерн» «Golden Hammer».
            0
            Поле CityId проиндексировано?
              0
              О, да!
                –3
                Я специализируюсь на MySQL, MSSQL видел только пару раз.
                  +1
                  пардон еще за один такой же вопрос. А Cities.Name проиндексирован?
                    0
                    А вы читать умеете?
                    Индексы на поля Cites.Id, Cites.Name, People.CityId – в наличии.
                      +1
                      Умею, пост был отредактирован.
                        0
                        Видел этот пост еще когда он был первым списке новых, эта информация уже была.
                +19
                А я думал, в статье и будет рассказано, как это сделать.
                  0
                  Кстати, если важно, чтобы такие запросы выполнялиссь быстро, можно попробовать OLAP.
                  Или я ошибаюсь?
                    0
                    В данном случае OLAP неприменим, так как речь, я полагаю, идет не о неком модуле статистики, а о прикладной задаче, которая должна работать с актуальными на текущий момент данными
                    0
                    Уже несколько раз сталкивался с такой задачей, и каждый раз писал велосипед. Последняя надежда на Хабр.
                    Сейчас решаю именно так, что сам пишу такие подзапросы.
                    –1
                    Почему не join'ите наоборот города right join persons?
                      +2
                      Потому что будет тоже самое. На всякий случай, только что это проверил )
                        –1
                        Да я про смысловую нагрузку — ведь ищете именно по городу…
                          +2
                          смысловая нагрузка — он ищет ЧЕЛОВЕКА. Он может приджоинить города и приджоинить воинские части и найти всех людей из Алматы, которые служили в морфлоте
                      +14
                      Во первых мне непонятно почему Left Join, вероятно именно из-за него оптимизатор не срабатывает, ибо понимает что c.Name может быть NULL, поэтому сканирует все 10млн записей для корректной сортировки. Inner Join не решает проблему?
                        +1
                        Да, Inner решает. Действительно, не дописал, что есть Null. Сейчас поправлю.
                          +1
                          NULL же не мешает делать выборку по Inner Join. Или нужны записи People, у которых CityId = NULL?
                            0
                            Логично, что нужны. «Правильного» решения для них нет.

                            «Неправильное» — это генерить отдельную вьюху, которая будет делать денормализацию (и подставлять пустые строки там, где null), и всю ее покрывать индексами. Тогда просядет все редактирование, но зато вот такие выборки будут летать.
                              +1
                              Ничего логичного, в задаче про это ничего не сказано. Можно UNION попробовать для двух селектов (один выбирает NULL'ы, второй делает Inner).
                                0
                                Во-первых, замучаешься строить union для всех таблиц в звезде (общий случай). Во-вторых, запросы поверх юниона делать неудобно и медленно.
                                  0
                                  Вы сейчас думаете о том как этом можно применить к общему случаю. Я понимаю, что это с одной стороны правильно, но задача стоит другая — нужно оптимизировать конкретный запрос. Поэтому все рассуждения поверх этого оторваны от задачи и к решению не имеют отношения. Главное — идея понятна (надеюсь) и в этом направлении есть возможность экспериментировать.
                                    0
                                    Я об этом думаю, потому что об этом думает автор: «Задача вполне реальная. Есть таблица с основной сущностью, от нее по принципу «звезда» отходит множество измерений. Пользователю нужно ее отобразить в гриде, предоставив сортировку по полям. „
                        +4
                        Никакой магии: 6 сек, как минимум, потому, что top 100 применяется ко всему результирущему набору.
                        Т.е. сначала сделается leftjoin 100млн * 10, затем отсортируется, затем от всего этого возьмется первые 100, остальные будут отброшены. Сервер оптимизирует как может, но все равно данных хватает на 6 секунд
                          +1
                          Попробуйте примерно так

                          with Data (
                          select t.*, ROW_NUMBER() over(ORDER BY Name DESC) as RN from
                          (select p.Name, c.Name as City from People p
                          left join Cities c on c.Id=p.CityId
                          order by c.Name) as t
                          )
                          select * from Data
                          where RN < 100;

                          Извлекает ровно 100, а не все и не 100тыс
                            0
                            Кажется будет тоже самое.
                            Сначала произойдёт соединение, потом отсортирует, а потом только выберет 100 первых по сортировке.
                              0
                              Немного подправил (в подзапросах с order обязательно должен быть TOP), и проверил. Выдает те-же 6 сек.
                              План запроса говорит, что сперва отрабатывает полностью и независимо внутренний подзапрос.
                              +3
                              Прошу прощения, но откуда 1 млрд. записей, там ведь left а не cross join?
                                0
                                Да, конечно, вы правы, там 100млн. Сорри, вечер после работы )
                              0
                              Вроде как с подобным бороться радикальными способами — не создавать nullable полей.
                              Во всех таблицах на которые есть ссылки создается запись с ID 0, а потом в связанных таблицах используется 0 вместо null, при этом индексы начинают работать.
                                0
                                насколько я помню, в нашей таблице поле, на которое джоинится — NOT NULL и все равно такая беда
                                  0
                                  И главное, не понятно: почему наличие Null и LeftJoin изменяет ситуацию? Ну добавили еще одно значение, и поместили его в начало отсортированного списка.
                                  0
                                  Возможен ли следующий запрос в MSSQL?
                                  select top 100 p.Name, c.Name as City from People p
                                  left join (select * FROM Cities order by Name) c on c.Id=p.CityId
                                    +5
                                    Мдя, туплю…
                                    0
                                    а почему не "...order by p.CityId "? Вам обязательно нужна сортировка по алфавиту?
                                      +1
                                      А какой вообще смысл в сортировке по ключу?
                                        0
                                        иначе мне кажется сервер сделает сортировку по p.Id, что не соответсвтует желаемому
                                      0
                                      А если View сделать и из нее Top 100 выбирать?
                                      Не помню, к сожалению, можно ли во View еще и индекс делать.
                                        0
                                        Если сделать вьюшку schema-bound и в ней будет уникальный ключ — можно будет и индекс по ней построить
                                          0
                                          Ага. Ключ без проблем создается (от жителя взять).
                                          Тогда с индексом мухой выбираться должно.
                                        +1
                                        Сейчас, догенерирую тестовые данные и посмотрим…
                                          –2
                                          Не очень понятен смысл такой выборки. Поэтому и решение предложить трудно. Сформулируйте задачу.
                                            +2
                                            Что тут непонятного? Нужно выбрать данные из таблицы, отсортированные по полю из другой таблице, связанной по форейн кею. Имхо ооочень распространенная задача.
                                              –21
                                              Если речь об общем случае, то нужно тупо денормализовать базу и внести поле city_name в таблицу people.

                                              Иначе, сервер будет всегда шастать по всей таблице people и состыковывать каждую ее запись с каждой внешней и только потом сортировать и отбрасывать. Индекс нифига не поможет.

                                              ЗЫ Одноименное поле («name») — это зло.
                                              ЗЫЫ Название таблицы во множественном числе (People, Cities) — это зло в квадрате.
                                              ЗЫЫЫ Ключевое поле таблицы («id») без имени таблицы — это зло в кубе.
                                                +17
                                                ваши ЗЫ непонятны, неаргументированны и 99%, что неправильны
                                                  0
                                                  Да, денормализация в данном случае поможет, а если нужно сортировать + еще вытягивать n полей по лефт джойнам?
                                                    –2
                                                    Так вытягивайте, кто мешает?

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

                                                    Главное, что индекс по внесенному полю отменил полный перебор записей в основной (большой) таблицы. Все остальные операции по сравнению с этим перебором блекнут…
                                                      0
                                                      вот нельзя денормализовать так просто
                                                      город пусть он втащит, но большинство сущностей именно сущности а не одно поле.
                                                      у меня например надо было сделать грид, в котором отображаются кроме полей собственно документа, еще именна статуса, назначенные пользователи ит д. и они могут быть как назначены так и не назначены, а грид сортировать надо, причем по каждой колонке
                                                    0
                                                    все ваше зло — ничто, и более того — добро, если пользуешься ОРМ.
                                                    Вы же пользуетесь ORM, правда?:)
                                                      –11
                                                      ORM — это зло в периоде! Нужен немного другой подход.

                                                      Мои рекомендации выстраданы во множестве проектов…
                                                        +4
                                                        У вас nickname в тему.
                                                      –4
                                                      ЗЫЫЫ Называть таблицы и поля с заглавной буквы — это тоже зло.

                                                      И, кстати, если не ошибаюсь, при сортировке по возрастанию MS SQL загоняет NULL в конец (как будто они больше всех), что возможно не следует логике приложения.

                                                      То есть при сортировке по возрастанию, в каком-то смысле логично получить вначале людей, вообще не привязанных к городу…

                                                        +3
                                                        есть nulls first, nulls last при oreder by
                                                          0
                                                          MS SQL при сортировке по возрастанию записывает NULL в начало выборки, якобы это минимальное значение.
                                                          0
                                                          А почему одноименное имя — зло? Имхо, City.Name вполне нормально и очевидно читается.

                                                          Число мы тоже стараемся использовать единственное, согласен.

                                                          А вот ключевое имя — да, стремимся имя таблицы выключать: CityID. В тоже время не вижу страшного в случае сокращенного написания («ID») в случае чрезмерно длинного названия таблицы: если DriverDocumentID — это нормально, то DriverrToDriverDocumentID — уже перебор (пример условный, конечно).
                                                            0
                                                            Не хочется долго распространятся, приведу идеальный (для меня) вариант:

                                                            CREATE TABLE city (
                                                            city_id,
                                                            city_name
                                                            )

                                                            CREATE TABLE user (
                                                            usr_id,
                                                            usr_name,
                                                            home_city REFERENCES city
                                                            )

                                                            И теперь не нужны точки и нет пересечений имен:

                                                            SELECT usr_id, usr_name, city_name FROM user
                                                            LEFT JOIN city ON home_city = city_id

                                                              0
                                                              Ну не знаю… По моему, порожденные свойства в классах будут выглядеть не ахти. user.usr_name — брр. Хотя понятно, что в ORM'е все можно переименовать, но все-таки.

                                                              Хотя понятно, что на вкус и на цвет товарищей нет, и главное — чтобы вся команда придерживалась единого стиля.
                                                                0
                                                                Вы хотите сказать, что ORM строит имя именно так?.. Это ужасно тогда. Вот почему:

                                                                CREATE TABLE city (
                                                                city_id,
                                                                city_name
                                                                )

                                                                CREATE TABLE user (
                                                                usr_id,
                                                                usr_name,
                                                                home_city REFERENCES city,
                                                                current_city REFERENCES city
                                                                )

                                                                SELECT usr_id, usr_name, city_name FROM user
                                                                LEFT JOIN city ON home_city = city_id
                                                                LEFT JOIN city ON current_city = city_id

                                                                Как теперь отличить имя города-происхождения от имени текущего города?.. По логике ORM это всегда «city.city_name» получается?

                                                                ЗЫ В моей библиотеке это будет: home_city_name и current_city_name
                                                                  0
                                                                  Там надо отталкиваться от того, что сама логика работы с ORM'ом основывается на работе с объектами, а не с результатами выполнения запросов. Так что нет ничего страшного в том, что в двух разных объектах имеются одинаковые поля.

                                                                  Так что будет City.Name, User.Name, или User.City.Name если мы обращаемся к названию города текущего пользователя.
                                                                    0
                                                                    >Так что нет ничего страшного в том, что в двух разных объектах имеются одинаковые поля.

                                                                    А зачастую это ещё и дюже удобно:

                                                                    for city in [User.HomeCity, User.CurrentCity]
                                                                    print city.id, city.name
                                                                    0
                                                                    Ну и, соответственно, в вашем примере — User.HomeCity.Name, User.CurrentCity.Name.
                                                                      +3
                                                                      Не, ну навскидку:
                                                                      CREATE TABLE supir_pupir_prefix_cities (
                                                                        id,
                                                                        name
                                                                      )
                                                                      
                                                                      CREATE TABLE supir_pupir_prefix_users (
                                                                        id,
                                                                        name,
                                                                        home_city REFERENCES supir_pupir_prefix_cities,
                                                                        current_city REFERENCES supir_pupir_prefix_cities
                                                                      )
                                                                      
                                                                      SELECT
                                                                        user.id,
                                                                        user.name,
                                                                        home_city.name,
                                                                        current_city.name
                                                                      FROM supir_pupir_prefix_users AS user
                                                                      LEFT JOIN supir_pupir_prefix_cities AS home_city ON user.home_city = home_city.id
                                                                      LEFT JOIN supir_pupir_prefix_cities AS current_city ON user.current_city = current_city.id
                                                                      
                                                                    +1
                                                                    Я считаю, что нужно home_city изменить на city_id.
                                                                    Для меня важно не пересечение имен, а наглядность соотвествия.
                                                                      0
                                                                      Или city_fk
                                                                      home_city выглядит как связывание по значению, не по абстрактному ключу.
                                                                      0
                                                                      когда имена таблицы и полей не больше четырёх символов, то это красиво и логично смотрится :)
                                                                      а если имена таблиц состоят из трёх-четырёх длинных слов, то имена полей будут состоять уже из семи-восьми слов? :)
                                                                      TABLE process_customer(
                                                                      process_customer_process_id,

                                                                      )
                                                                        +3
                                                                        Во, я ждал аргументации :) Не нужны точки — это по вашему весомый аргумент? :)
                                                                        SELECT
                                                                          user_id,
                                                                          user_name,
                                                                          city_name
                                                                        FROM user
                                                                        LEFT JOIN city ON home_city = city_id
                                                                        SELECT
                                                                          user.id,
                                                                          user.name,
                                                                          city.name
                                                                        FROM user
                                                                        LEFT JOIN city ON home_city = city.id
                                                                        

                                                                        Однако-же
                                                                        SELECT user_name FROM user WHERE user_id = 5
                                                                        SELECT name FROM user WHERE id = 5

                                                                        Остальные правила я так понимаю произрастают из этого.
                                                                      0
                                                                      ыыы… а какая разница, как названы таблицы и поля? :)
                                                                      да хоть циферьками, всё равно обращение к ним из кода идёт по именованым константам или переменным, и только в одном месте.
                                                                        0
                                                                        использование атомов ( tenshi.habrahabr.ru/blog/97670/ ) позволяет не заморачиваться с инфраструктурой именованных констант и находить места использования каждого поля простым поиском по исходникам.
                                                                    +1
                                                                    «select * from People p
                                                                    left join Cities c on c.Id=p.CityId
                                                                    where p.CityId
                                                                    in (select top 1 id from Cities order by Name)
                                                                    order by c.[Name] „

                                                                    Что-то я вообще не понимаю такой оптимизации…
                                                                    Зачем отобранных людей из данного одного города сортировать по имени этого города?
                                                                    Оно же будет одинаковым у всех выбранных записей…
                                                                    0
                                                                    Покажите, пожалуйста, план выполнения запроса и список всех индексов по данным таблицам.
                                                                      0
                                                                      Я имел ввиду план который можно прочитать, а то на картинке ничего не прочитать.
                                                                    0
                                                                    Добавьте дополнительное условие в первый WHERE, например AND CityId IS NOT NULL. Условие должно быть обязательно по индексированному полю!
                                                                    Не знаю как работает оптимизатор запросов в MSSQL, но в PostgreSQL, на больших таблицах, такой «финт ушами» позволяет уменьшить время выполнения запроса на 3 порядка.
                                                                      0
                                                                      Не проще ли тогда заменить Left Join на Inner Join??? Но автору, как я понял, надо именно с NULLами, поэтому метод не катит…
                                                                        +1
                                                                        может тогда (People InnerJoin Cities) UNION (People WHEW CityID IS NULL)?
                                                                          0
                                                                          NULL теоретически должен изди первым…
                                                                          Только надо убедится что сортировка будет выполнятся до юниона а лимит после. Например, в MySQL SELECT field FROM t1 UNION SELECT field FROM t2 ORDER BY field LIMIT 100 выберет 100 записаей, но листаться и объединятся будут все, т.к. ORDER сработает после UNION, незнаю решат ли проблему скобочки, можно попробовать сделать что-то типа SELECT field FROM t1 UNION SELECT * FROM ( SELECT field FROM t2 ORDER BY field) tt LIMIT 100
                                                                            0
                                                                            Результат сравнения NULL _теоретически_ (по стандарту) с чем бы то ли было — Unknown, т.о. порядок их вмешания в общую кучу неопределен. Конкретно для MSSQL можно даже включить режим соответствия стандарту через SET ANSI NULL.

                                                                            Другое дело, что да, большинство серверов плюют на стандарт и дают некую стабильность такой сортировки, что приводит к таким вот решениям :(
                                                                          0
                                                                          Какой там джойн без разницы… Главное применить дополнительный фильтр по индексированному полю.
                                                                          В чем суть запросов как у автора: поскольку нет дополнительных полей фильтрации, оптимизатор выбирает самую простую методику — full join + sequence scan по обоим таблица. А поскольку sequence scan очень не быстрая операция (еще бы, поднять с жесткого диска таблицу в 10 млн. записей), то и запрос получается очень медленным. При дополнительном фильтре получает index scan по большой таблице и, соответственно, join результатов с меньшей таблицей, отсюда и скорость выполнения (индекс зачастую помещается полностью в память, как и результат таких join-ов).
                                                                        +4
                                                                        вот такая штука получилась:
                                                                        Таблички
                                                                        — CREATE TABLE [dbo].[Cities] (
                                                                        [Id] uniqueidentifier NOT NULL PRIMARY KEY,
                                                                        [Name] nvarchar(50) NOT NULL,
                                                                        )
                                                                        ON [PRIMARY]
                                                                        GO
                                                                        CREATE TABLE [dbo].[People] (
                                                                        [Id] uniqueidentifier NOT NULL PRIMARY KEY,
                                                                        [Name] nvarchar(50) NOT NULL,
                                                                        [CityId] UNIQUEIDENTIFIER FOREIGN KEY REFERENCES dbo.Cities (id)
                                                                        )
                                                                        ON [PRIMARY]
                                                                        GO
                                                                        Запрос:
                                                                        — SELECT TOP 100 People.NAME, dbo.Cities.[Name]
                                                                        FROM dbo.Cities JOIN people ON cities.Id = people.cityid
                                                                        ORDER BY dbo.Cities.[Name]
                                                                        — (100 row(s) affected)
                                                                        SQL Server Execution Times:
                                                                        CPU time = 16 ms, elapsed time = 5 ms.
                                                                        -----
                                                                          +1
                                                                          а если CityId будет NULL?
                                                                            +1
                                                                            А в какое место выборки при сортировке по городу вставлять «бомжей» тогда? :)
                                                                              +1
                                                                              Туда же, куда вставляется NULL при любой другой сортировке
                                                                                0
                                                                                тогда я предлагаю выбрать их отдельно, присоединить юнионом и поместить в нужную позицию.
                                                                                  0
                                                                                  нужно подумать и попробовать) а потом еще протолкнуть через Linq:)
                                                                                  0
                                                                                  Вы ведь в курсе, что по стандарту результат сравнения NULL с любыми другими операндами — Unknown? Т.е. даже NULL = NULL — это Unknown, а уж NULL < 'строка' — подавно.

                                                                                  Сделано это на самом деле не потому, что люди, писавшие стандарт такие вредные, а именно для того, чтобы избежать такого abuse, которое хочет устроить автор топика. Вот везде логично предлагают делать явный UNION и пропихивать эти дополнительные строчки именно в то место топпинга, в котором они нужны.
                                                                                    +1
                                                                                    select * from emp order by sal desc NULLS FIRST;
                                                                                    select * from emp order by sal desc NULLS LAST;


                                                                                    Это Oracle. В MsSql не уверен, но тоже думаю, что проблем с сортировкой нет.
                                                                                      0
                                                                                      В MSSQL там прибит определенный порядок, в противоречии со спецификацией. Эту «приятную особенность» можно даже выключить (через SET ANSI NULLS), но так почти никто не делает.

                                                                                      Вопрос в том, что это хак — со всеми вытекающими последствиями. Тот, кто им пользуется, должен быть готов к тому, что в том числе будет такой план выполнения запроса, что всё будет медленно и печально.
                                                                                0
                                                                                Сделать ещё
                                                                                UNION SELECT TOP 100 People.NAME, NULL
                                                                                FROM people WHERE people.cityid IS NULL

                                                                                и из этого всего выбрать TOP100.

                                                                                Как идея? :)
                                                                                  0
                                                                                  Надо пробовать:)
                                                                                0
                                                                                  0
                                                                                  у вас точно 10 млн people?
                                                                                    0
                                                                                    SET STATISTICS TIME ON;
                                                                                    SELECT COUNT(*) FROM dbo.Cities;
                                                                                    SELECT COUNT(*) FROM people;
                                                                                    SELECT TOP 100 People.NAME, dbo.Cities.[Name]
                                                                                    FROM people RIGHT JOIN dbo.Cities ON dbo.Cities.Id = people.cityid
                                                                                    ORDER BY dbo.Cities.NAME desc;

                                                                                    — SQL Server parse and compile time:
                                                                                    CPU time = 0 ms, elapsed time = 0 ms.

                                                                                    SQL Server Execution Times:
                                                                                    CPU time = 0 ms, elapsed time = 0 ms.
                                                                                    SQL Server parse and compile time:
                                                                                    CPU time = 5 ms, elapsed time = 5 ms.

                                                                                    SQL Server Execution Times:
                                                                                    CPU time = 0 ms, elapsed time = 0 ms.

                                                                                    — 100

                                                                                    (1 row(s) affected)

                                                                                    (1 row(s) affected)

                                                                                    SQL Server Execution Times:
                                                                                    CPU time = 0 ms, elapsed time = 1 ms.

                                                                                    — 10000000

                                                                                    (1 row(s) affected)

                                                                                    (1 row(s) affected)

                                                                                    SQL Server Execution Times:
                                                                                    CPU time = 1875 ms, elapsed time = 952 ms.
                                                                                    NAME Name
                                                                                    — — Annette Wallace149
                                                                                    Holly059 Wallace149
                                                                                    <<>>
                                                                                    Mike8 Wallace149

                                                                                    (100 row(s) affected)

                                                                                    (1 row(s) affected)

                                                                                    SQL Server Execution Times:
                                                                                    CPU time = 0 ms, elapsed time = 150 ms.
                                                                                    SQL Server parse and compile time:
                                                                                    CPU time = 0 ms, elapsed time = 0 ms.

                                                                                    SQL Server Execution Times:
                                                                                    CPU time = 0 ms, elapsed time = 0 ms.

                                                                                      +1
                                                                                      Ой. А тут я не прав.
                                                                                  0
                                                                                  Мы ведь знаем, что в первых 100 записях будет исключительно Алматы! Ведь записей – 10 миллионов, и значит на город приходится по 100 тыс. (...) Почему SQL сервер, обладая статистикой, не делает так (...)

                                                                                  Попробую объяснить.
                                                                                  Он предполагает (вполне логично), что в первых записях может и не найтись 100 жителей, поэтому и выбирает параллельно, чтобы быстрее отдать результат.
                                                                                  Если вы уверены, что всегда найдётся точно больше 100 записей для одного города — напишите хранимку, в которой вытяните ID города, и по CityID достаньте, что надо.
                                                                                    0
                                                                                    В Вашем плане наибольшую стоимость имеет сортировка.
                                                                                    Предлагаю сделать кластеризованный индекс по CityId в таблице People. В таблице City города пересортировать чтобы первый по алфавитому порядку имели бы меньший Id.
                                                                                    В запросе выбирать первые 100 записей из People а затем join-ить с City чтобы получить наименование городов.
                                                                                    Имхо, это должно помочь оптимизатору с сортировкой.
                                                                                      +5
                                                                                      интересно а расплодившиеся на хабре ms евангелисты почтут за честь помочь с проблемкой или в обычной манере продолжат ездить по ушам?
                                                                                        0
                                                                                        ночь на дворе, а на урале тем более
                                                                                        завтра утром встанут, прочитают и ответят
                                                                                        +1
                                                                                        Извеняюсь я мускульный человек, а можно сделать запрос на запрос?

                                                                                        SELECT TOP 100 *
                                                                                        FROM (

                                                                                        select * from People p
                                                                                        left join Cities c on c.Id=p.CityId
                                                                                        where p.CityId
                                                                                        in (select top 1 id from Cities order by Name)
                                                                                        order by c.[Name]

                                                                                        ) all_people

                                                                                        П.С. В Мускуле всречался с похожей проблемой, выходил из неё именно селектором на селектор
                                                                                          +1
                                                                                          Думаю, что можно. Но приведенный запрос справедлив лишь для истинно равномерного распределения. Если бы автор был уверен в том, что данные действительно всегда равномерно распределены, то он использовал бы подобный запрос. В общем случае, автор надеется что сервер поймёт какое распределение у данных и воспользуется этим. А если через секунду распределение измениться, а план выполнения запроса уже закешировался? Серверу дороже каждый раз переоценивать распределение всех данных, чем сформировать универсальный план.
                                                                                            0
                                                                                            Да, именно это автору и нужно! )
                                                                                            И автор готов рискнуть тем, что за секунду такое распределение не изменится. Ведь именно для этих целей и придумали статистику, не правда ли?
                                                                                            Пусть сервер строит запросы по статистике а я клятвенно обещаю ее раз в сутки честно пересчитывать.
                                                                                              0
                                                                                              Только, наверное, раз в секунду пересчитывать, а не раз в сутки, вот в чем беда.
                                                                                          0
                                                                                          Положите город в таблицу с людьми прямо текстом ;-) Лучшее решение. Ну или используйте foreign key'и.
                                                                                            0
                                                                                            > Нужно выбрать первых 100 записей People, отсортированных по Cites.

                                                                                            Что это за выборка? В чем ее смысл? Сто Аайрон Аайронсонов из Алма-аты?

                                                                                            Или это чисто теоретическая задача?
                                                                                              0
                                                                                              Задача вполне реальная. Есть таблица с основной сущностью, от нее по принципу «звезда» отходит множество измерений. Пользователю нужно ее отобразить в гриде, предоставив сортировку по полям.

                                                                                              Начиная с некоторого размера основной таблицы сортировка сводится к тому, что выбирается окно с одинаковыми (крайними) значениями, (вроде «Алматы») но при этом система начинает жутко тормозить.

                                                                                              –1
                                                                                              Сделайте денормализацию вашей базы данных, добавьте в таблицу People поле CityName.
                                                                                                0
                                                                                                а если таких полей десяток?
                                                                                                –1
                                                                                                Мдас, ну не получается селектом, напиши процедуру, ведь MSSQL это умеет.
                                                                                                  +1
                                                                                                  Поле City.Name для Person`а не проиндексировано, именно поэтому на sort уходит 99%.

                                                                                                  Его конечно и невозможно проиндексировать, но можно изъе… ся. Будем надеяться, что у нас один язык (русский к примеру или английский), т.е. не i18n.

                                                                                                  При создании таблицы Cities и прочих тупеньких справочников а ля Id, Name, вставляем данные, упорядочив их по Name`у. Таким образом Id`шники будут тоже упорядочены.

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

                                                                                                  А уже в самом запросе делаем любые join`ы, но order by идёт по Person.CityId.

                                                                                                  Вот когда в SQL`ях можно будет создвать индексы на поля в других таблицах — проблема убежит. Хотя м.б. кто-то уже так умеет.
                                                                                                    0
                                                                                                    Id — Guid. Не так то просто его поп орядку расположить при вставке
                                                                                                      0
                                                                                                      А, вижу.

                                                                                                      Для данного подхода guid излишен — для таких малых справочников integer`а хватит.

                                                                                                      Хотя я тут ещё вариант подумал — «типа» денормализация, как выше товарищ предлагал.

                                                                                                      Сделать view`шку, в которой заджойнить City.Name, и уже в этой вьюшке его проиндексировать. По-мойму в SQL-сервере это возможно.
                                                                                                        0
                                                                                                        guid здесь не излишен — идентификатор создается на клиенте, а серверов несколько. как будете бороться с колизиями?
                                                                                                        0
                                                                                                        Почитайте про sequential guid. Некоторые ОРМы их потдерживают. Например НХибирнейт.
                                                                                                        0
                                                                                                        В таблице в реальности есть множество свойств. А ID можно отсортировать только по одному из них.
                                                                                                          0
                                                                                                          Тогда думаю надо двигаться в сторону «денормализации» и создать indexed view типа VPeople, в котором будет CityName и по которой будет индекс.
                                                                                                        0
                                                                                                        Я хз че тут понаворочено, но замечаю, что избавляемся от LEFT JOIN где только можно.
                                                                                                        Всегда можно быстро выгребсти отсортированный список городов (а можно еще до кучи закешить города->количество_пиплов), взять первый, а потом выгрести из пиплов столько сколько нужно вторым запросом по этому городу.
                                                                                                          0
                                                                                                          «Интересно, что ДАЖЕ ЕСЛИ поле City было бы NotNull но использовался LeftJoin – то запрос тормозит. „
                                                                                                          Как верно написали выше, Left Join автоматически приводит к выводу всей таблицы. Поэтому вы всегда сначала выбираете весь people, а потом всегда его пересортировываете.

                                                                                                          Поэтому — медленно.
                                                                                                            +1
                                                                                                            первоначальный запрос выберет 100 записей людей из первого города, если не найдет доберет оставшихся из второго города и так далее.

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

                                                                                                            если это не подходит, можно, сосчитав count(*) ом количество людей по городам, сделать select from people where cityid in(… )

                                                                                                            количество вернувшихся записей — можно отсекать в коде. в вернувшемся курсоре проходить по нужному кол-ву записей, потом курсор закрывать. это должно быть быстрее, чем top c fullscan-ом вдогонку.

                                                                                                            PS я сначала написал, а потом только прочитал предыдущий комментарий :)
                                                                                                              0
                                                                                                              Народ, а почему никто не смотрит на план выполнения запроса? Он же не просто так приведен.
                                                                                                              Смотрим — насколько я понимаю (не спец в SQLServer), он делает Full Scan Cities, затем по индексу приджойнивает таблицу People.
                                                                                                              А нам, по идее, — нужно сделать наоборот — один раз пройтись по People, при этом джойня (по индексу) таблицу Cities, затем отсортировать и выбрать 100 первых.

                                                                                                              В оракле было бы так:

                                                                                                              select person, city from
                                                                                                              (select /*+ ordered use_nl(p c) index(c cities$cityid) */ 
                                                                                                              rownum r, p.name person, c.name city
                                                                                                              from person p left join cities c on p.cityid = c.cityid
                                                                                                              order by c.name)
                                                                                                              where r <= 100
                                                                                                              


                                                                                                              p.s.: сущности именуются в именительном падеже (City, а не Cities)
                                                                                                                0
                                                                                                                Вообще, есть правило — при джойне таблиц, различающихся в несколько раз, один проход надо проводить по большой таблице. Тогда будет быстро.
                                                                                                                  0
                                                                                                                  СУБД должна сама делать такой выбор, на то у нее статистика есть
                                                                                                                  +3
                                                                                                                  «насколько я понимаю (не спец в SQLServer), он делает Full Scan Cities, затем по индексу приджойнивает таблицу People.»
                                                                                                                  А вы неправильно понимаете. Он одновременно читает две таблицы полностью, потом делает джойн. Почему он читает Cities целиком? Потому что у него есть статистика, которая говорит, что будут задействованы все значения, а не только часть — поэтому выгоднее прочитать сто строк в память.

                                                                                                                  " один раз пройтись по People, при этом джойня (по индексу) таблицу Cities, затем отсортировать и выбрать 100 первых."
                                                                                                                  Вот он так и делает, только Cities берет не по индексу с диска, а из памяти (что эффективнее).

                                                                                                                  «сущности именуются в именительном падеже (City, а не Cities)»
                                                                                                                  А не надо путать падеж и число. И соглашений об именовании таблиц в базе, как бы, больше одной.
                                                                                                                    0
                                                                                                                    А, тут же не nested_loops, а hash join. Тогда да — один раз прочитать то, один раз другое, и джойн по хешу.

                                                                                                                    «Потому что у него есть статистика, которая говорит, что будут задействованы все значения, а не только часть — поэтому выгоднее прочитать сто строк в память.» — сто каких строк он будет читать? Сто первых строк из Cities? Сомневаюсь.
                                                                                                                      0
                                                                                                                      «сто каких строк он будет читать? Сто первых строк из Cities? Сомневаюсь. „
                                                                                                                      Все строки из cities — их там всего сто.
                                                                                                                        0
                                                                                                                        а, точно. Тогда да.
                                                                                                                  0
                                                                                                                  как насчет group by?
                                                                                                                    0
                                                                                                                    а точнее?
                                                                                                                    0
                                                                                                                    вместо order в конце сделать group by по городам. а вообще постараться уйти от джойнов. возможно просто select distinct. у нас же нет условия уникальности на выходе…
                                                                                                                      0
                                                                                                                      как уйти от джойнов, если таблицы связаны?
                                                                                                                      0
                                                                                                                      Если честно, то предложенное решение очень костылявое — в исходном запросе order by nulls last и order by nulls first дадут разные результаты.

                                                                                                                      А если NULLы не нужны — зачем заморачиваться с left join'aми — inner join и будет быстро работать.

                                                                                                                      select top 100
                                                                                                                       p.name person, c.name city
                                                                                                                      from person p, cities c 
                                                                                                                      where p.cityid = c.cityid
                                                                                                                      order by c.name
                                                                                                                      
                                                                                                                        0
                                                                                                                        Чуть ниже есть еще один мой длинный комментарий, однако, увидев этот пост, хочу к нему тоже добавиться ;)
                                                                                                                        По, идее, такой запрос решит проблему «бомжей»:

                                                                                                                        select top 100
                                                                                                                        	person
                                                                                                                        	, city
                                                                                                                        from 
                                                                                                                        	(
                                                                                                                        		select top 100
                                                                                                                        			p.name person
                                                                                                                        			, c.name city
                                                                                                                        		from
                                                                                                                        			person p
                                                                                                                        			, cities c 
                                                                                                                        		where
                                                                                                                        			p.cityid = c.cityid
                                                                                                                        		order by
                                                                                                                        			city
                                                                                                                        			, person
                                                                                                                        	)
                                                                                                                        	union (
                                                                                                                        		select top 100
                                                                                                                        			p.name person
                                                                                                                        			, null city
                                                                                                                        		from
                                                                                                                        			person p
                                                                                                                        		where
                                                                                                                        			p.cityid is null
                                                                                                                        		order by
                                                                                                                        			person
                                                                                                                        	)
                                                                                                                        order by
                                                                                                                        	city
                                                                                                                        	, person
                                                                                                                        

                                                                                                                        0
                                                                                                                        Ниже много букв:

                                                                                                                        Решать такую задачу чисто на языке SQL — нерационально (особенно, учитывая факт, что оптимизатор SQL не справляется).
                                                                                                                        Однако из чисто академических интересов, попробуем решить задачу, подсказав оптимизатору последовательность запросов.

                                                                                                                        Общий план таков:
                                                                                                                        1) считаем кол-во жителей в каждом городе
                                                                                                                        2) отбираем минимально достаточное количество городов, в алфавитном порядке так,
                                                                                                                        чтобы суммарное количество в них было как раз больше 100, но при удалении хоть
                                                                                                                        одного города меньше 100
                                                                                                                        3) из полученного списка городов, отбираем всех жителей и выводим первые 100

                                                                                                                        Стадия 1. Посчитаем количество жителей в каждом городе.

                                                                                                                        create table tmp as
                                                                                                                        select
                                                                                                                            Cities.Id
                                                                                                                            , Cities.Name
                                                                                                                            , cnt.people
                                                                                                                        from    
                                                                                                                            (
                                                                                                                                select 
                                                                                                                                    CityId
                                                                                                                                    , count(Name) people
                                                                                                                                from 
                                                                                                                                    People
                                                                                                                                group by
                                                                                                                                    CityId
                                                                                                                            ) as cnt
                                                                                                                            join Cities on (Cities.Id = cnt.CityId)
                                                                                                                        


                                                                                                                        Стадия 2. отбираем минимально достаточное количество городов

                                                                                                                        create table enough as
                                                                                                                        select
                                                                                                                            t2.Id as Id
                                                                                                                            , max(t2.Name) as Name
                                                                                                                            , sum(t1.people)+t2.people as people
                                                                                                                        from
                                                                                                                            tmp t1,
                                                                                                                            join tmp t2 on (t1.Name < t2.Name)
                                                                                                                        group by
                                                                                                                            t2.Id
                                                                                                                        having
                                                                                                                            sum(t1.people) < 100
                                                                                                                        


                                                                                                                        Стадия 3. выводим жителей

                                                                                                                        select
                                                                                                                                top 100 p.Name PersonName
                                                                                                                                , c.Name CityName
                                                                                                                        from
                                                                                                                                People p
                                                                                                                                join enough c on p.CityId = c.Id
                                                                                                                        order by
                                                                                                                                c.Name
                                                                                                                                , p.Name
                                                                                                                        


                                                                                                                        Несколько замечаний:
                                                                                                                        * Создание временных табилц можно не делать, но тогда вместо из названия в тех местах, где они используются надо подставить сами запросы — SQL получится многоэтажным :)
                                                                                                                        * Все выше написанное — теория — проверить не могу — нет MSSQL'я
                                                                                                                        * Если в таблице enough нет 100 жителей, то придется еще такую структуру добавить:

                                                                                                                        select
                                                                                                                            top 100 Name PersonName
                                                                                                                            , Name CityName
                                                                                                                        from
                                                                                                                            (select *** запрос на Стадии 3 (см.выше) ***) 
                                                                                                                            union (select top 100 Name as PersonName, null as CityName from People where IdCity is null)
                                                                                                                        order by
                                                                                                                                CityName
                                                                                                                                , PersonName
                                                                                                                        


                                                                                                                        P.S. может у кого-то хватит терпения проверить? ;-) А если даст положительный результат — объединить все запросы в один, еще раз проверить, постануть его сюда и отчитаться…

                                                                                                                        Only users with full accounts can post comments. Log in, please.